
\chapter{Mathematical formulas as code. II. Mathematical induction\label{chap:2-Mathematical-induction}}

\global\long\def\pplus{{\displaystyle }{+\negmedspace+}}%
We will now study more flexible ways of working with data collections
in the functional programming paradigm. The Scala standard library
has methods for performing general iterative computations, that is,
computations defined by induction. Translating mathematical induction
into code is the focus of this chapter.

First, we need to become fluent in using tuple types with Scala collections.

\section{Tuple types}

\subsection{Examples of using tuples}

Many standard library methods in Scala work with \index{tuples}tuple
types. A simple example of a tuple is a \emph{pair} of values, e.g.,
a pair of an integer and a string. The Scala syntax for this type
of pair is
\begin{lstlisting}
val a: (Int, String) = (123, "xyz")
\end{lstlisting}
The type expression \lstinline!(Int, String)! denotes the type of
this pair.

A \textbf{triple} is defined in Scala like this:
\begin{lstlisting}
val b: (Boolean, Int, Int) = (true, 3, 4)
\end{lstlisting}
Pairs and triples are examples of tuples. A \textbf{tuple} can contain
any number of values, which may be called \textbf{parts\index{tuples!parts}}
of a tuple (they are also called \textbf{fields} of\index{tuples!fields}
a tuple). The parts of a tuple can have different types, but the type
of each part is fixed once and for all. Also, the number of parts
in a tuple is fixed. It is a \textbf{type error}\index{type error}
to use incorrect types in a tuple, or an incorrect number of parts
of a tuple:
\begin{lstlisting}
scala> val bad: (Int, String) = (1,2)
<console>:11: error: type mismatch;
 found   : Int(2)
 required: String
       val bad: (Int, String) = (1,2)
                                   ^
scala> val bad: (Int, String) = (1,"a",3)
<console>:11: error: type mismatch;
 found   : (Int, String, Int)
 required: (Int, String)
       val bad: (Int, String) = (1,"a",3)
                                ^
\end{lstlisting}
Parts of a tuple can be accessed by number, starting from $1$. The
Scala syntax for \textbf{tuple accessor\index{tuples!accessors}}
methods looks like \lstinline!._1!, for example:
\begin{lstlisting}
scala> val a = (123, "xyz")
a: (Int, String) = (123,xyz)

scala> a._1
res0: Int = 123

scala> a._2
res1: String = xyz 
\end{lstlisting}
It is a type error to access a tuple part that does not exist:
\begin{lstlisting}
scala> a._0
<console>:13: error: value _0 is not a member of (Int, String)
       a._0
         ^

scala> a._5
<console>:13: error: value _5 is not a member of (Int, String)
       a._5
         ^
\end{lstlisting}
Type errors\index{type error} are detected at compile time, before
any computations begin.

Tuples can be \textbf{nested}\index{tuples!nested}: any part of a
tuple can be itself a tuple:
\begin{lstlisting}
scala> val c: (Boolean, (String, Int), Boolean) = (true, ("abc", 3), false)
c: (Boolean, (String, Int), Boolean) = (true,(abc,3),false)

scala> c._1
res0: Boolean = true

scala> c._2
res1: (String, Int) = (abc,3)
\end{lstlisting}

To define functions whose arguments are tuples, we could use the tuple
accessors. An example of such a function is
\begin{lstlisting}
def f(p: (Boolean, Int), q: Int): Boolean = p._1 && (p._2 > q) 
\end{lstlisting}
The first argument, \lstinline!p!, of this function, has a tuple
type. The function body uses accessor methods (\lstinline!._1! and
\lstinline!._2!) to compute the result value. Note that the second
part of the tuple \lstinline!p! is of type \lstinline!Int!, so it
is valid to compare it with an integer \lstinline!q!. It would be
a \index{type error}type error to compare the \emph{tuple} \lstinline!p!
with an \emph{integer} using the expression \lstinline!p > q!. It
would be also a type error to apply the function \lstinline!f! to
an argument \lstinline!p! that has a wrong type, e.g., the type \lstinline!(Int, Int)!
instead of \lstinline!(Boolean, Int)!.

\subsection{Pattern matching for tuples}

Instead of using accessor methods when working with tuples, it is
often convenient to use \textbf{pattern matching\index{pattern matching}}.
Pattern matching occurs in two situations in Scala:
\begin{itemize}
\item destructuring definition: \lstinline[mathescape=true]!val $pattern$ = ...!
\item \lstinline!case! expression: \lstinline[mathescape=true]!case $pattern$ => ...!
\end{itemize}
\begin{wrapfigure}{l}{0.295\columnwidth}%
\vspace{-0.8\baselineskip}
\begin{lstlisting}
scala> val g = (1, 2, 3)
g: (Int, Int, Int) = (1,2,3)

scala> val (x, y, z) = g
x: Int = 1
y: Int = 2
z: Int = 3
\end{lstlisting}
\vspace{-1.5\baselineskip}
\end{wrapfigure}%

An example of a \textbf{destructuring\index{destructuring} definition}
is shown at left. The value \lstinline!g! is a tuple of three integers.
After defining \lstinline!g!, we define the three variables \lstinline!x!,
\lstinline!y!, \lstinline!z! \emph{at once} in a single \lstinline!val!
definition. We imagine that this definition \textsf{``}destructures\textsf{''} the
data structure contained in \lstinline!g! and decomposes it into
three parts, then assigns the names \lstinline!x!, \lstinline!y!,
\lstinline!z! to these parts. The types of \lstinline!x!, \lstinline!y!,
\lstinline!z! are also assigned automatically.

In the example above, the left-hand side of the destructuring definition
contains a tuple pattern \lstinline!(x, y, z)! that looks like a
tuple, except that its parts are names \lstinline!x!, \lstinline!y!,
\lstinline!z! that are so far \emph{undefined}. These names are called
\index{pattern variables}\textbf{pattern variables}. The destructuring
definition checks whether the structure of the value of \lstinline!g!
\textsf{``}matches\textsf{''} the given pattern. (If \lstinline!g! does not contain
a tuple with exactly three parts, the definition will fail.) This
computation is called \textbf{pattern matching}\index{pattern matching}.

Pattern matching is often used for working with tuples. The expression
\lstinline!{case (a, b, c) => ...}!\begin{wrapfigure}{l}{0.6\columnwidth}%
\vspace{-0.7\baselineskip}
\begin{lstlisting}
scala> (1, 2, 3) match { case (a, b, c) => a + b + c }
res0: Int = 6
\end{lstlisting}
\vspace{-1.5\baselineskip}
\end{wrapfigure}%
called a \textbf{case expression}\index{case expression@\texttt{case} expression}
(shown at left) performs pattern matching on its argument. The pattern
matching will \textsf{``}destructure\textsf{''} (i.e., decompose) a tuple and try
to match it to the given pattern \lstinline!(a, b, c)!. In this pattern,
\lstinline!a!, \lstinline!b!, \lstinline!c! are as yet undefined
new variables, \textemdash{} that is, they are \index{pattern variables}pattern
variables. If the pattern matching succeeds, the pattern variables
\lstinline!a!, \lstinline!b!, \lstinline!c! are assigned their
values, and the function body can proceed to perform its computation.
In this example, the pattern variables \lstinline!a!, \lstinline!b!,
\lstinline!c! will be assigned values $1$, $2$, and $3$, and so
the expression evaluates to $6$.

Pattern matching is especially convenient for nested tuples. Here
is an example where a nested tuple \lstinline!p! is destructured
by pattern matching:\hfill{}~\begin{wrapfigure}{L}{0.54\columnwidth}%
\vspace{-0.8\baselineskip}
\begin{lstlisting}
def t1(p: (Int, (String, Int))): String = p match {
  case (x, (str, y)) => str + (x + y).toString
}

scala> t1((10, ("result is ", 2)))
res0: String = result is 12
\end{lstlisting}
\vspace{-1.5\baselineskip}
\end{wrapfigure}%
\textbf{ }

\noindent The type structure of the argument \lstinline!(Int, (String, Int))!
is visually repeated in the pattern \lstinline!(x, (str, y))!, making
it clear that \lstinline!x! and \lstinline!y! become integers and
\lstinline!str! becomes a string after pattern matching.

If we rewrite the code of \lstinline!t1! using the tuple accessor
methods instead of pattern matching, the code will look like this:
\begin{lstlisting}
def t2(p: (Int, (String, Int))): String = p._2._1 + (p._1 + p._2._2).toString
\end{lstlisting}
This code is shorter but harder to read. For example, it is not immediately
clear that \lstinline!p._2._1! is a string. It is also harder to
modify this code: Suppose we want to change the type of the tuple
\lstinline!p! to \lstinline!((Int, String), Int)!. Then the new
code is
\begin{lstlisting}
def t3(p: ((Int, String), Int)): String = p._1._2 + (p._1._1 + p._2).toString
\end{lstlisting}
It takes time to verify, by going through every accessor method, that
the function \lstinline!t3! computes the same expression as \lstinline!t2!.
In contrast, the code is changed easily when using the pattern matching
expression instead of the accessor methods:\hfill{}~\begin{wrapfigure}{L}{0.54\columnwidth}%
\vspace{-0.8\baselineskip}
\begin{lstlisting}
def t4(p: ((Int, String), Int)): String = p match {
  case ((x, str), y) => str + (x + y).toString
}
\end{lstlisting}
\vspace{-0.6\baselineskip}
\end{wrapfigure}%

\noindent The only change in the function body, compared to \lstinline!t1!,
is in the pattern matcher. It is visually clear that \lstinline!t4!
computes the same expression as \lstinline!t1!.

Sometimes we do not need some of the tuple parts in a pattern match.
The following syntax is used to make this intention clear:

\begin{wrapfigure}{L}{0.54\columnwidth}%
\vspace{-0.8\baselineskip}
\begin{lstlisting}
scala> val (x, _, _, z) = ("abc", 123, false, true)
x: String = abc
z: Boolean = true
\end{lstlisting}
\vspace{-0.6\baselineskip}
\end{wrapfigure}%

\noindent The underscore symbol (\lstinline!_!) denotes the parts
of the pattern that we want to ignore. The underscore will always
match any value regardless of its type.

A shorter syntax for functions such as \lstinline!{case (x, y) => y}!
that extract elements from tuples \lstinline!(t => t._2)!, as illustrated
here:
\begin{lstlisting}
scala> val p: ((Int, Int )) => Int = { case (x, y) => y }
p: ((Int, Int)) => Int = <function1>

scala> p((1, 2))
res0: Int = 2

scala> val q: ((Int, Int )) => Int = (t => t._2)
q: ((Int, Int)) => Int = <function1>

scala> q((1, 2))
res1: Int = 2

scala> Seq( (1,10), (2,20), (3,30) ).map(t => t._2)
res2: Seq[Int] = List(10, 20, 30)
\end{lstlisting}


\subsection{Using tuples with collections}

Tuples can be combined with any other types without restrictions.
For instance, we can define a tuple of functions,
\begin{lstlisting}
val q: (Int => Int, Int => Int) = (x => x + 1, x => x - 1)
\end{lstlisting}
We can create a list of tuples,
\begin{lstlisting}
val r: List[(String, Int)] = List(("apples", 3), ("oranges", 2), ("pears", 0))
\end{lstlisting}
We could define a tuple of lists of tuples of functions, or any other
combination.

Here is an example of using the standard method \lstinline!map! to
transform a list of tuples. The argument of \lstinline!map! must
be a function taking a tuple as its argument. It is convenient to
use pattern matching for writing such functions:
\begin{lstlisting}
scala> val basket: List[(String, Int)] = List(("apples", 3), ("pears", 2), ("lemons", 0))
basket: List[(String, Int)] = List((apples,3), (pears,2), (lemons,0))

scala> basket.map { case (fruit, count) => count * 2 }
res0: List[Int] = List(6, 4, 0)

scala> basket.map { case (fruit, count) => count * 2 }.sum
res1: Int = 10
\end{lstlisting}
In this way, we can use the standard methods such as \lstinline!map!,
\lstinline!filter!, \lstinline!max!, \lstinline!sum! to manipulate
sequences of tuples. The names of the pattern variables \textsf{``}\lstinline!fruit!\textsf{''},
\textsf{``}\lstinline!count!\textsf{''} are chosen to help us remember the meaning
of the parts of tuples.

We can easily transform a list of tuples into a list of values of
a different type:
\begin{lstlisting}
scala> basket.map { case (fruit, count) =>
  val isAcidic = (fruit == "lemons")
  (fruit, isAcidic)
}
res2: List[(String, Boolean)] = List((apples,false), (pears,false), (lemons,true)) 
\end{lstlisting}
In the Scala syntax, a nameless function written with braces \lstinline!{ ... }!
can define local values in its body. The return value of the function
is the last expression written in the function body. In this example,
the return value of the nameless function is the tuple \lstinline!(fruit, isAcidic)!.

\subsection{Treating dictionaries as collections}

In the Scala standard library, tuples are frequently used as types
of intermediate values. For instance, tuples are used when iterating
over dictionaries. The Scala type \lstinline!Map[K,V]! represents
a dictionary with keys of type \lstinline!K! and values of type \lstinline!V!.
Here \lstinline!K! and \lstinline!V! are \textbf{type parameters\index{type parameter}}.
Type parameters represent unknown types that will be chosen later,
when working with values having specific types.

In order to create a dictionary with given keys and values, we can
write
\begin{lstlisting}
Map(("apples", 3), ("oranges", 2), ("pears", 0))
\end{lstlisting}
The same result is obtained by first creating a sequence of key/value
\emph{pairs} and then converting that sequence into a dictionary via
the method \lstinline!toMap!:
\begin{lstlisting}
List(("apples", 3), ("oranges", 2), ("pears", 0)).toMap
\end{lstlisting}
The same method works for other collection types such as \lstinline!Seq!,
\lstinline!Vector!, \lstinline!Stream!, and \lstinline!Array!. 

The Scala library defines a special infix syntax for pairs via the
arrow symbol \lstinline!->!. The expression \lstinline!x -> y! is
equivalent to the pair \lstinline!(x, y)!:
\begin{lstlisting}
scala> "apples" -> 3
res0: (String, Int) = (apples,3)
\end{lstlisting}
With this syntax, the code for creating a dictionary is easier to
read:
\begin{lstlisting}
Map("apples" -> 3, "oranges" -> 2, "pears" -> 0)
\end{lstlisting}

The method \lstinline!toSeq! converts a dictionary into a sequence
of pairs:
\begin{lstlisting}
scala> Map("apples" -> 3, "oranges" -> 2, "pears" -> 0).toSeq
res20: Seq[(String, Int)] = ArrayBuffer((apples,3), (oranges,2), (pears,0))
\end{lstlisting}
The \lstinline!ArrayBuffer! is one of the many list-like data structures
in the Scala library. All these data structures are subtypes of the
common \textsf{``}sequence\textsf{''} type \lstinline!Seq!. The methods defined in
the Scala standard library sometimes return different implementations
of the \lstinline!Seq! type for reasons of performance.

The standard library has several useful methods that use tuple types,
such as \lstinline!map! and \lstinline!filter! (with dictionaries),
\lstinline!toMap!, \lstinline!zip!, and \lstinline!zipWithIndex!.
The methods \lstinline!flatten!, \lstinline!flatMap!, \lstinline!groupBy!,
and \lstinline!sliding! also work with most collection types, including
dictionaries and sets. It is important to become familiar with these
methods, because it will help writing code that uses sequences, sets,
and dictionaries. Let us now look at these methods one by one.

\paragraph*{The \texttt{map} and \texttt{toMap} methods}

Chapter~\ref{chap:1-Values,-types,-expressions,} showed how the
\lstinline!map! method works on sequences: the expression \lstinline!xs.map(f)!
applies a given function \lstinline!f! to each element of the sequence
\lstinline!xs!, gathering the results in a new sequence. In this
sense, we can say that the \lstinline!map! method \textsf{``}iterates over\textsf{''}
sequences. The \lstinline!map! method works similarly on dictionaries,
except that iterating over a dictionary of type \lstinline!Map[K, V]!
when applying \lstinline!map! looks like iterating over a sequence
of \emph{pairs}, \lstinline!Seq[(K, V)]!. If \lstinline!d: Map[K, V]!
is a dictionary, the argument \lstinline!f! of \lstinline!d.map(f)!
must be a function operating on tuples of type \lstinline!(K, V)!.
Typically, such functions are written using \lstinline!case! expressions:
\begin{lstlisting}
val fruitBasket = Map("apples" -> 3, "pears" -> 2, "lemons" -> 0)

scala> fruitBasket.map { case (fruit, count) => count * 2 }
res0: Seq[Int] = ArrayBuffer(6, 4, 0)
\end{lstlisting}
When using \lstinline!map! to transform a dictionary into a sequence
of pairs, the result is again a dictionary. But when any intermediate
result is not a sequence of pairs, we may need to use \lstinline!toMap!:
\begin{lstlisting}
scala> fruitBasket.map { case (fruit, count) => (fruit, count * 2) }
res1: Map[String,Int] = Map(apples -> 6, pears -> 4, lemons -> 0)

scala> fruitBasket.map { case (fruit, count) => (fruit, count, count*2) }.
         map { case (fruit, _, count2) => (fruit, count2 / 2) }.toMap
res2: Map[String,Int] = Map(apples -> 3, pears -> 2, lemons -> 0)
\end{lstlisting}


\paragraph*{The \texttt{filter} method }

works on dictionaries by iterating on key/value pairs. The filtering
predicate must be a function of type \lstinline!((K, V)) => Boolean!.
For example:
\begin{lstlisting}
scala> fruitBasket.filter { case (fruit, count) => count > 0 }
res2: Map[String,Int] = Map(apples -> 3, pears -> 2)
\end{lstlisting}


\paragraph*{The \texttt{zip} and \texttt{zipWithIndex} methods}

The \lstinline!zip! method takes \emph{two} sequences and produces
a sequence of pairs, taking one element from each sequence:
\begin{lstlisting}
scala> val s = List(1, 2, 3)
s: List[Int] = List(1, 2, 3)

scala> val t = List(true, false, true)
t: List[Boolean] = List(true, false, true)

scala> s.zip(t)
res3: List[(Int, Boolean)] = List((1,true), (2,false), (3,true))

scala> s zip t
res4: List[(Int, Boolean)] = List((1,true), (2,false), (3,true)) 
\end{lstlisting}
In the last line, the equivalent \textsf{``}dotless\textsf{''} infix syntax (\lstinline!s zip t!)
is shown to illustrate a syntax convention of Scala that we will sometimes
use.

The \lstinline!zip! method works equally well on dictionaries: in
that case, dictionaries are automatically converted to sequences of
pairs before applying \lstinline!zip!.

The \lstinline!zipWithIndex! method transforms a sequence into a
sequence of pairs, where the second part of the pair is the zero-based
index:
\begin{lstlisting}
scala> List("a", "b", "c").zipWithIndex
res5: List[(String, Int)] = List((a,0), (b,1), (c,2)) 
\end{lstlisting}


\paragraph*{The \texttt{flatten} method}

converts nested sequences to \textsf{``}flattened\textsf{''} ones:
\begin{lstlisting}
scala> List(List(1, 2), List(2, 3), List(3, 4)).flatten
res6: List[Int] = List(1, 2, 2, 3, 3, 4)
\end{lstlisting}
The \textsf{``}flattening\textsf{''} operation computes the concatenation of the inner
sequences. In Scala, sequences are concatenated using the operation
\lstinline!++!, e.g.:
\begin{lstlisting}
scala> List(1, 2, 3) ++ List(4, 5, 6) ++ List(0)
res7: List[Int] = List(1, 2, 3, 4, 5, 6, 0)
\end{lstlisting}
So the \lstinline!flatten! method inserts the operation \lstinline!++!
between all the inner sequences.

Keep in mind that \lstinline!flatten! removes \emph{only one} level
of nesting, which is at the \textsf{``}outside\textsf{''} of the data structure. If
applied to a \lstinline!List[List[List[Int]]]!, the \lstinline!flatten!
method returns a \lstinline!List[List[Int]]!:
\begin{lstlisting}
scala> List(List(List(1), List(2)), List(List(2), List(3))).flatten
res8: List[List[Int]] = List(List(1), List(2), List(2), List(3))
\end{lstlisting}


\paragraph*{The \texttt{flatMap} method}

is closely related to \lstinline!flatten! and can be seen as a shortcut,
equivalent to first applying \lstinline!map! and then \lstinline!flatten!:
\begin{lstlisting}
scala> List(1,2,3,4).map(n => (1 to n).toList)
res9: List[List[Int]] = List(List(1), List(1, 2), List(1, 2, 3), List(1, 2, 3, 4))

scala> List(1,2,3,4).map(n => (1 to n).toList).flatten
res10: List[Int] = List(1, 1, 2, 1, 2, 3, 1, 2, 3, 4)

scala> List(1,2,3,4).flatMap(n => (1 to n).toList)
res11: List[Int] = List(1, 1, 2, 1, 2, 3, 1, 2, 3, 4)
\end{lstlisting}
The \lstinline!flatMap! operation transforms a sequence by mapping
each element to a potentially different number of new elements.

At first sight, it may be unclear why \lstinline!flatMap! is useful.
(Should we perhaps combine \lstinline!filter! and \lstinline!flatten!
into a \textsf{``}\lstinline!flatFilter!\textsf{''}, or combine \lstinline!zip!
and \lstinline!flatten! into a \textsf{``}\lstinline!flatZip!\textsf{''}?) However,
we will see later in this book that the use of \lstinline!flatMap!,
which is related to \textsf{``}monads\textsf{''}\index{monads}, is one of the most
versatile and powerful design patterns in functional programming.
In this chapter, several examples and exercises will illustrate the
use of \lstinline!flatMap! for working on sequences.

\paragraph*{The \texttt{groupBy} method}

rearranges a sequence into a dictionary where some elements of the
original sequence are grouped together into subsequences. For example,
given a sequence of words, we can group all words that start with
the letter \lstinline!"y"! into one subsequence, and all other words
into another subsequence. This is accomplished by the following code,
\begin{lstlisting}
scala> Seq("wombat", "xanthan", "yogurt", "zebra").groupBy(s => if (s startsWith "y") 1 else 2)
res12: Map[Int,Seq[String]] = Map(1 -> List(yogurt), 2 -> List(wombat, xanthan, zebra))
\end{lstlisting}
The argument of the \lstinline!groupBy! method is a \emph{function}
that computes a \textsf{``}key\textsf{''} out of each sequence element. The key can
have an arbitrarily chosen type. (In the current example, that type
is \lstinline!Int!.) The result of \lstinline!groupBy! is a dictionary
that maps each key to the sub-sequence of values that have that key.
(In the current example, the type of the dictionary is therefore \lstinline!Map[Int, Seq[String]]!.)
The order of elements in the sub-sequences remains the same as in
the original sequence.

As another example of using \lstinline!groupBy!, the following code
will group together all numbers that have the same remainder after
division by $3$:
\begin{lstlisting}
scala> List(1,2,3,4,5).groupBy(k => k % 3)
res13: Map[Int,List[Int]] = Map(2 -> List(2, 5), 1 -> List(1, 4), 0 -> List(3))
\end{lstlisting}


\paragraph*{The \texttt{sliding} method}

creates a sequence of sliding windows of a given width:
\begin{lstlisting}
scala> (1 to 10).sliding(4).toList
res14: List[IndexedSeq[Int]] = List(Vector(1, 2, 3, 4), Vector(2, 3, 4, 5), Vector(3, 4, 5, 6), Vector(4, 5, 6, 7), Vector(5, 6, 7, 8), Vector(6, 7, 8, 9), Vector(7, 8, 9, 10))
\end{lstlisting}
After creating a nested sequence, we can apply an aggregation operation
to the inner sequences. For example, the following code computes a
sliding-window average with window width $50$ over an array of $100$
numbers:
\begin{lstlisting}
scala> (1 to 100).map(x => math.cos(x)).sliding(50).map(_.sum / 50).take(5).toList
res15: List[Double] = List(-0.005153079196990285, -0.0011160413780774369, 0.003947079736951305, 0.005381273944717851, 0.0018679497047270743)
\end{lstlisting}


\paragraph*{The \texttt{sortBy} method}

sorts a sequence according to a sorting key. The argument of \lstinline!sortBy!
is a \emph{function} that computes the sorting key from a sequence
element. In this way, we can sort elements in an arbitrary way:
\begin{lstlisting}
scala> Seq(1, 2, 3).sortBy(x => -x)
res0: Seq[Int] = List(3, 2, 1)

scala> Seq("xx", "z", "yyy").sortBy(word => word)        // Sort alphabetically.
res1: Seq[String] = List(xx, yyy, z)

scala> Seq("xx", "z", "yyy").sortBy(word => word.length) // Sort by word length.
res2: Seq[String] = List(z, xx, yyy)
\end{lstlisting}
Sorting by the elements themselves, as we have done here with \lstinline!.sortBy(word => word)!,
is only possible if the element\textsf{'}s type has a well-defined ordering.
For strings, this is the alphabetic ordering, and for integers, the
standard arithmetic ordering. For such types, a convenience method
\lstinline!sorted! is defined, and works equivalently to \lstinline!sortBy(x => x)!:
\begin{lstlisting}
scala> Seq("xx", "z", "yyy").sorted
res3: Seq[String] = List(xx, yyy, z)
\end{lstlisting}


\subsection{Solved examples: Tuples and collections\index{solved examples}}

\subsubsection{Example \label{enu:tuples-Example1-for}\ref{enu:tuples-Example1-for}}

For a given sequence $x_{i}$, compute the sequence of pairs $b_{i}=\left(\cos x_{i},\sin x_{i}\right)$.

Hint: use \lstinline!map!, assume \lstinline!xs:Seq[Double]!.

\subparagraph{Solution}

We need to produce a sequence that has a pair of values corresponding
to each element of the original sequence. This transformation is exactly
what the \lstinline!map! method does. So the code is
\begin{lstlisting}
xs.map { x => (math.cos(x), math.sin(x)) }
\end{lstlisting}


\subsubsection{Example \label{enu:tuples-Example2}\ref{enu:tuples-Example2}}

Count how many times $\cos x_{i}>\sin x_{i}$ occurs in a sequence
$x_{i}$.

Hint: use \lstinline!count!, assume \lstinline!xs: Seq[Double]!.

\subparagraph{Solution }

The method \lstinline!count! takes a predicate and returns the number
of sequence elements for which the predicate is \lstinline!true!:
\begin{lstlisting}
xs.count { x => math.cos(x) > math.sin(x) }
\end{lstlisting}
We could also reuse the solution of Exercise~\ref{enu:tuples-Example1-for}
that computed the cosine and the sine values. The code would then
become
\begin{lstlisting}
xs.map { x => (math.cos(x), math.sin(x)) }
  .count { case (cosine, sine) => cosine > sine }
\end{lstlisting}


\subsubsection{Example \label{enu:tuples-Example3}\ref{enu:tuples-Example3}}

For given sequences $a_{i}$ and $b_{i}$, compute the sequence of
differences $c_{i}=a_{i}-b_{i}$.

Hint: use \lstinline!zip!, \lstinline!map!, and assume \lstinline!as!
and \lstinline!bs! are of type \lstinline!Seq[Double]!.

\subparagraph{Solution }

We can use \lstinline!zip! on \lstinline!as! and \lstinline!bs!,
which gives a sequence of pairs,
\begin{lstlisting}
as.zip(bs): Seq[(Double, Double)]
\end{lstlisting}
We then compute the differences $a_{i}-b_{i}$ by applying \lstinline!map!
to this sequence:
\begin{lstlisting}
as.zip(bs).map { case (a, b) => a - b }
\end{lstlisting}


\subsubsection{Example \label{enu:tuples-Example4-in}\ref{enu:tuples-Example4-in}}

In a given sequence $p_{i}$, count how many times $p_{i}>p_{i+1}$
occurs.

Hint: use \lstinline!zip! and \lstinline!tail!.

\subparagraph{Solution}

Given \lstinline!ps:Seq[Double]!, we can compute \lstinline!ps.tail!.
The result is a sequence that is $1$ element shorter than \lstinline!ps!,
for example:
\begin{lstlisting}
scala> val ps = Seq(1,2,3,4)
ps: Seq[Int] = List(1, 2, 3, 4)

scala> ps.tail
res0: Seq[Int] = List(2, 3, 4)
\end{lstlisting}
Taking a \lstinline!zip! of the two sequences \lstinline!ps! and
\lstinline!ps.tail!, we get a sequence of pairs:
\begin{lstlisting}
scala> ps.zip(ps.tail)
res1: Seq[(Int, Int)] = List((1,2), (2,3), (3,4))
\end{lstlisting}
Note that \lstinline!ps.tail! is $1$ element shorter than \lstinline!ps!,
and the resulting sequence of pairs is also $1$ element shorter than
\lstinline!ps!. In other words, it is not necessary to truncate \lstinline!ps!
before computing \lstinline!ps.zip(ps.tail)!. Now apply the \lstinline!count!
method:

\begin{lstlisting}
ps.zip(ps.tail).count { case (a, b) => a > b }
\end{lstlisting}


\subsubsection{Example \label{subsec:tuples-Example5}\ref{subsec:tuples-Example5}}

For a given $k>0$, compute the sequence $c_{i}=\max(b_{i-k},...,b_{i+k})$.

\subparagraph{Solution}

Applying the \lstinline!sliding! method to a list gives a list of
nested lists:
\begin{lstlisting}
scala> val bs = List(1,2,3,4,5)
bs: List[Int] = List(1, 2, 3, 4, 5)

scala> bs.sliding(3).toList
res0: List[List[Int]] = List(List(1, 2, 3), List(2, 3, 4), List(3, 4, 5)) 
\end{lstlisting}
For each $b_{i}$, we need to obtain a list of $2k+1$ nearby elements
$\left(b_{i-k},...,b_{i+k}\right)$. So we need to use \lstinline!.sliding(2 * k + 1)!
to obtain a window of the required size. Now we can compute the maximum
of each of the nested lists by using the \lstinline!map! method on
the outer list, with the \lstinline!max! method applied to the nested
lists. So the argument of the \lstinline!map! method must be the
function \lstinline!nested => nested.max!:

\begin{lstlisting}
bs.sliding(2 * k + 1).map(nested => nested.max)
\end{lstlisting}
In Scala, this code can be written more concisely using the syntax
\begin{lstlisting}
bs.sliding(2 * k + 1).map(_.max)
\end{lstlisting}
because the syntax \lstinline!_.max! means the nameless function
\lstinline!x => x.max!.

\subsubsection{Example \label{subsec:tuples-Example6}\ref{subsec:tuples-Example6}}

Create a $10\times10$ multiplication table as a dictionary of type
\lstinline!Map[(Int, Int), Int]!. For example, a $3\times3$ multiplication
table would be given by this dictionary,
\begin{lstlisting}
Map( (1, 1) -> 1, (1, 2) -> 2, (1, 3) -> 3, (2, 1) -> 2,
  (2, 2) -> 4, (2, 3) -> 6, (3, 1) -> 3, (3, 2) -> 6, (3, 3) -> 9 )
\end{lstlisting}

Hint: use \lstinline!flatMap! and \lstinline!toMap!.

\subparagraph{Solution}

We are required to make a dictionary that maps pairs of integers \lstinline!(x, y)!
to \lstinline!x * y!. Begin by creating the list of \emph{keys} for
that dictionary, which must be a list of pairs \lstinline!(x, y)!
of the form \lstinline!List((1,1), (1,2), ..., (2,1), (2,2), ...)!.
We need to iterate over a sequence of values of \lstinline!x!; and
for each \lstinline!x!, we then need to iterate over another sequence
to provide values for \lstinline!y!. Try this computation:
\begin{lstlisting}
scala> val s = List(1, 2, 3).map(x => List(1, 2, 3))
s: List[List[Int]] = List(List(1, 2, 3), List(1, 2, 3), List(1, 2, 3))
\end{lstlisting}
We would like to get \lstinline!List((1,1), (1,2), 1,3))! etc., and
so we use \lstinline!map! on the inner list with a nameless function
\lstinline!y => (1, y)! that converts a number into a tuple,

\begin{wrapfigure}{l}{0.6\columnwidth}%
\vspace{-0.75\baselineskip}
\begin{lstlisting}
scala> List(1, 2, 3).map { y => (1, y) }
res0: List[(Int, Int)] = List((1,1), (1,2), (1,3))
\end{lstlisting}
\vspace{-1.5\baselineskip}
\end{wrapfigure}%

\noindent The curly braces in \lstinline!{y => (1, y)}! are only
for clarity; we could also use parentheses and write \lstinline!(y => (1, y))!. 

Now, we need to have \lstinline!(x, y)! instead of \lstinline!(1, y)!
in the argument of \lstinline!map!, where \lstinline!x! iterates
over \lstinline!List(1, 2, 3)! in the outside scope. Using this \lstinline!map!
operation, we obtain
\begin{lstlisting}
scala> val s = List(1, 2, 3).map(x => List(1, 2, 3).map { y => (x, y) })
s: List[List[(Int, Int)]] = List(List((1,1), (1,2), (1,3)), List((2,1), (2,2), (2,3)), List((3,1), (3,2), (3,3)))
\end{lstlisting}
This is almost what we need, except that the nested lists need to
be concatenated into a single list. This is exactly what \lstinline!flatten!
does:
\begin{lstlisting}
scala> val s = List(1, 2, 3).map(x => List(1, 2, 3).map { y => (x, y) }).flatten
s: List[(Int, Int)] = List((1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3))
\end{lstlisting}
It is shorter to write \lstinline!.flatMap(...)! instead of \lstinline!.map(...).flatten!:
\begin{lstlisting}
scala> val s = List(1, 2, 3).flatMap(x => List(1, 2, 3).map { y => (x, y) })
s: List[(Int, Int)] = List((1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)) 
\end{lstlisting}
This is the list of keys for the required dictionary. The dictionary
needs to map each \emph{pair} of integers \lstinline!(x, y)! to \lstinline!x * y!.
To create that dictionary, we will apply \lstinline!toMap! to a sequence
of pairs \lstinline!(key, value)!, which in our case needs to be
of the form of a nested tuple \lstinline!((x, y), x * y)!. To achieve
this, we use \lstinline!map! with a function that computes the product
and creates these nested tuples:
\begin{lstlisting}
scala> val s = List(1, 2, 3).flatMap(x => List(1, 2, 3).map { y => (x, y) }).
  map { case (x, y) => ((x, y), x * y) }
s: List[((Int, Int), Int)] = List(((1,1),1), ((1,2),2), ((1,3),3), ((2,1),2), ((2,2),4), ((2,3),6), ((3,1),3), ((3,2),6), ((3,3),9))
\end{lstlisting}
We can simplify this code if we notice that we are first mapping each
\lstinline!y! to a tuple \lstinline!(x, y)!, and later map each
tuple \lstinline!(x, y)! to a nested tuple \lstinline!((x, y), x * y)!.
Instead, the entire computation can be done in the inner \lstinline!map!
operation:
\begin{lstlisting}
scala> val s = List(1, 2, 3).flatMap(x => List(1, 2, 3).map { y => ((x, y), x * y) } )
s: List[((Int, Int), Int)] = List(((1,1),1), ((1,2),2), ((1,3),3), ((2,1),2), ((2,2),4), ((2,3),6), ((3,1),3), ((3,2),6), ((3,3),9))
\end{lstlisting}
It remains to convert this list of tuples to a dictionary with \lstinline!toMap!.
Also, for better readability, we can use Scala\textsf{'}s pair syntax, \lstinline!key -> value!,
which is equivalent to writing the tuple \lstinline!(key, value)!:

\begin{lstlisting}
(1 to 10).flatMap(x => (1 to 10).map { y => (x, y) -> x * y }).toMap
\end{lstlisting}


\subsubsection{Example \label{subsec:tuples-Example7}\ref{subsec:tuples-Example7}}

For a given sequence $x_{i}$, compute the maximum of all of the numbers
$x_{i}$, $x_{i}^{2}$, $\cos x_{i}$, $\sin x_{i}$. Hint: use \lstinline!flatMap!,
\lstinline!max!.

\subparagraph{Solution}

We will compute the required value if we take \lstinline!max! of
a list containing all of the numbers. To do that, first map each element
of the list \lstinline!xs: Seq[Double]! into a sequence of three
numbers:
\begin{lstlisting}
scala> val xs = List(0.1, 0.5, 0.9)         // An example list of some `Double` numbers.
xs: List[Double] = List(0.1, 0.5, 0.9)

scala> xs.map { x => Seq(x, x*x, math.cos(x), math.sin(x)) }
res0: List[Seq[Double]] = List(List(0.1, 0.010000000000000002, 0.9950041652780258, 0.09983341664682815), List(0.5, 0.25, 0.8775825618903728, 0.479425538604203), List(0.9, 0.81, 0.6216099682706644, 0.7833269096274834))
\end{lstlisting}
This list is almost what we need, except we need to \lstinline!flatten!
it:
\begin{lstlisting}
scala> res0.flatten
res1: List[Double] = List(0.1, 0.010000000000000002, 0.9950041652780258, 0.09983341664682815, 0.5, 0.25, 0.8775825618903728, 0.479425538604203, 0.9, 0.81, 0.6216099682706644, 0.7833269096274834) 
\end{lstlisting}
It remains to take the maximum of the resulting numbers:
\begin{lstlisting}
scala> res1.max
res2: Double = 0.9950041652780258
\end{lstlisting}
The final code (starting from a given sequence \lstinline!xs!) is

\begin{lstlisting}
xs.flatMap { x => Seq(x, x*x, math.cos(x), math.sin(x)) }.max
\end{lstlisting}


\subsubsection{Example \label{subsec:tuples-Example8}\ref{subsec:tuples-Example8}}

From a dictionary of type \lstinline!Map[String, String]! mapping
names to addresses, and assuming that the addresses do not repeat,
compute a dictionary of type \lstinline!Map[String, String]! mapping
the addresses back to names. 

\subparagraph{Solution}

Keep in mind that iterating over a dictionary looks like iterating
over a list of \lstinline!(key, value)! pairs:

\begin{lstlisting}
dict.map { case (name, addr) => (addr, name) }
\end{lstlisting}


\subsubsection{Example \label{subsec:tuples-Example-9}\ref{subsec:tuples-Example-9}}

Write the solution of Example~\ref{subsec:tuples-Example8} as a
function with type parameters \lstinline!Name! and \lstinline!Addr!
instead of the fixed type \lstinline!String!.

\subparagraph{Solution}

In Scala, the syntax for type parameters in a function definition
is
\begin{lstlisting}
def rev[Name, Addr](...) = ...
\end{lstlisting}
The type of the argument is \lstinline!Map[Name, Addr]!, while the
type of the result is \lstinline!Map[Addr, Name]!. So we use the
type parameters \lstinline!Name! and \lstinline!Addr! in the type
signature of the function. The final code is
\begin{lstlisting}
def rev[Name, Addr](dict: Map[Name, Addr]): Map[Addr, Name] =
  dict.map { case (name, addr) => (addr, name) }
\end{lstlisting}
The body of the function \lstinline!rev! remains the same as in Example~\ref{subsec:tuples-Example8};
only the type signature changed. This is because the procedure for
reversing a dictionary works in the same way for dictionaries of any
type. So the body of the function \lstinline!rev! does not actually
need to know the types of the keys and values in the dictionary. For
this reason, it was easy for us to change the specific type \lstinline!String!
into type parameters in that function.

When the function \lstinline!rev! is applied to a dictionary of a
specific type, the Scala compiler will automatically set the type
parameters \lstinline!Name! and \lstinline!Addr! that fit the required
types of the dictionary\textsf{'}s keys and values. For example, if we apply
\lstinline!rev! to a dictionary of type \lstinline!Map[Boolean, Seq[String]]!,
the type parameters will be set automatically as \lstinline!Name = Boolean!
and \lstinline!Addr = Seq[String]!:
\begin{lstlisting}
scala> val d = Map(true -> Seq("x", "y"), false -> Seq("z", "t"))
d: Map[Boolean, Seq[String]] = Map(true -> List(x, y), false -> List(z, t))

scala> rev(d)
res0: Map[Seq[String], Boolean] = Map(List(x, y) -> true, List(z, t) -> false)
\end{lstlisting}
Type parameters can be also set explicitly when using the function
\lstinline!rev!. If the type parameters are chosen incorrectly, the
program will not compile:
\begin{lstlisting}
scala> rev[Boolean, Seq[String]](d)
res1: Map[Seq[String],Boolean] = Map(List(x, y) -> true, List(z, t) -> false)

scala> rev[Int, Double](d)
<console>:14: error: type mismatch;
 found   : Map[Boolean,Seq[String]]
 required: Map[Int,Double]
       rev[Int, Double](d)
                        ^
\end{lstlisting}


\subsubsection{Example \label{subsec:tuples-Example10}\ref{subsec:tuples-Example10}{*}}

Given a sequence \lstinline!words: Seq[String]! of some \textsf{``}words\textsf{''},
compute a sequence of type \lstinline!Seq[(Seq[String], Int)]!, where
each inner sequence should contain all the words having the same length,
paired with the integer value showing that length. The resulting sequence
must be ordered by increasing length of words. So, the input \lstinline!Seq("the", "food", "is", "good")!
should produce 
\begin{lstlisting}
Seq((Seq("is"), 2), (Seq("the"), 3), (Seq("food", "good"), 4))
\end{lstlisting}


\subparagraph{Solution}

Begin by grouping the words by length. The library method \lstinline!groupBy!
takes a function that computes a grouping key from each element of
a sequence. To group by word length, which is computed with the method
\lstinline!length! if applied to a string, we write
\begin{lstlisting}
words.groupBy { word => word.length }
\end{lstlisting}
or, more concisely, \lstinline!words.groupBy(_.length)!. The result
of this expression is a dictionary that maps each length to the list
of words having that length:
\begin{lstlisting}
scala> words.groupBy(_.length)
res0: scala.collection.immutable.Map[Int,Seq[String]] = Map(2 -> List(is), 4 -> List(food, good), 3 -> List(the))
\end{lstlisting}
This is close to what we need. If we convert this dictionary to a
sequence, we will get a list of pairs
\begin{lstlisting}
scala> words.groupBy(_.length).toSeq
res1: Seq[(Int, Seq[String])] = ArrayBuffer((2,List(is)), (4,List(food, good)), (3,List(the))) 
\end{lstlisting}
It remains to swap the length and the list of words and to sort the
result by increasing length. We can do this in any order: first sort,
then swap; or first swap, then sort. The final code is
\begin{lstlisting}
words
  .groupBy(_.length)
  .toSeq
  .sortBy { case (len, words) => len }
  .map { case (len, words) => (words, len) }
\end{lstlisting}
This can be written somewhat shorter if we use the code \lstinline!_._1!
(equivalent to \lstinline!x => x._1!) for selecting the first parts
from pairs and \lstinline!swap! for swapping the two elements of
a pair:
\begin{lstlisting}
words.groupBy(_.length).toSeq.sortBy(_._1).map(_.swap)
\end{lstlisting}
However, the program may now be harder to read and to modify.

\subsection{Reasoning about type parameters in collections}

In Example~\ref{subsec:tuples-Example10} we have applied a chain
of operations to a sequence. Let us add comments showing the type
of the intermediate result after each operation:
\begin{lstlisting}
words // Seq[String]
  .groupBy(_.length)                         // Map[Int, Seq[String]]
  .toSeq                                     // Seq[ (Int, Seq[String]) ]
  .sortBy { case (len, words) => len }       // Seq[ (Int, Seq[String]) ]
  .map { case (len, words) => (words, len) } // Seq[ (Seq[String], Int) ]
\end{lstlisting}
In computations like this, the Scala compiler verifies at each step
that the operations are applied to values of the correct type.

For instance, \lstinline!sortBy! is defined for sequences but not
for dictionaries, so it would be a \index{type error}type error to
apply \lstinline!sortBy! to a dictionary without first converting
it to a sequence using \lstinline!toSeq!. The type of the intermediate
result after \lstinline!toSeq! is \lstinline!Seq[ (Int, Seq[String]) ]!,
and the \lstinline!sortBy! operation is applied to that sequence.
So the sequence element matched by \lstinline!{ case (len, words) => len }!
is a tuple \lstinline!(Int, Seq[String])!, which means that the pattern
variables \lstinline!len! and \lstinline!words! must have types
\lstinline!Int! and \lstinline!Seq[String]! respectively. It would
be a type error to use the sorting key function \lstinline!{ case (len, words) => words }!:
the sorting key can be an integer \lstinline!len!, but not a string
sequence \lstinline!words! (because sorting by string sequences is
not defined).

If we visualize how the type of the sequence should change at every
step, we can more quickly understand how to implement the required
task. Begin by writing down the intermediate types that would be needed
during the computation:
\begin{lstlisting}
words: Seq[String] // Need to group by word length.
Map[Int, Seq[String]]  // Need to sort by word length; can't sort a dictionary!
// Need to convert this dictionary to a sequence:
Seq[ (Int, Seq[String]) ] // Now sort this by the `Int` value. Sorting does not change the types.
// It remains to swap the parts of all tuples in the sequence:
Seq[ (Seq[String], Int) ] // We are done.
\end{lstlisting}
Having written down these types, we are better assured that the computation
can be done correctly. Writing the code becomes straightforward, since
we are guided by the already known types of the intermediate results:
\begin{lstlisting}
words.groupBy(_.length).toSeq.sortBy(_._1).map(_.swap)
\end{lstlisting}

This example illustrates the main benefits of reasoning about types:
it gives direct guidance about how to organize the computation, together
with a greater assurance in the correctness of the code.

\subsection{Exercises: Tuples and collections\index{exercises}}

\subsubsection{Exercise \label{tuples-Exercise-1}\ref{tuples-Exercise-1}}

Find all pairs $i,j$ within $\left(0,1,...,9\right)$ such that $i+4*j>i*j$.

Hint: use \lstinline!flatMap! and \lstinline!filter!.

\subsubsection{Exercise \label{tuples-Exercise-2}\ref{tuples-Exercise-2}}

Same task as in Exercise~\ref{tuples-Exercise-1}, but for $i,j,k$
and the condition $i+4*j+9*k>i*j*k$.

\subsubsection{Exercise \label{tuples-Exercise-3}\ref{tuples-Exercise-3}}

Given two sequences \lstinline!p: Seq[String]! and \lstinline!q: Seq[Boolean]!
of equal length, compute a \lstinline!Seq[String]! with those elements
of \lstinline!p! for which the corresponding element of \lstinline!q!
is \lstinline!true!.

Hint: use \lstinline!zip!, \lstinline!map!, \lstinline!filter!.

\subsubsection{Exercise \label{tuples-Exercise-4}\ref{tuples-Exercise-4}}

Convert a \lstinline!Seq[Int]! into a \lstinline!Seq[(Int, Boolean)]!
where the \lstinline!Boolean! value is \lstinline!true! when the
element is followed by a larger value. For example, the input sequence
\lstinline!Seq(1,3,2,4)! is to be converted into \lstinline!Seq((1,true),(3,false),(2,true),(4,false))!.
(The last element, 4, has no following element.)

\subsubsection{Exercise \label{tuples-Exercise-7}\ref{tuples-Exercise-7}}

Given \lstinline!p: Seq[String]! and \lstinline!q: Seq[Int]! of
equal length, compute a \lstinline!Seq[String]! that contains the
strings from \lstinline!p! ordered according to the corresponding
numbers from \lstinline!q!. For example, if \lstinline!p = Seq("a", "b", "c")!
and \lstinline!q = Seq(10, -1, 5)! then the result must be \lstinline!Seq("b", "c", "a")!.

\subsubsection{Exercise \label{tuples-Exercise-8}\ref{tuples-Exercise-8}}

Write the solution of Exercise~\ref{tuples-Exercise-7} as a function
with type parameter \lstinline!A! instead of the fixed type \lstinline!String!.
The required type signature and a sample test:
\begin{lstlisting}
def reorder[A](p: Seq[A], q: Seq[Int]): Seq[A] = ???    // In Scala, ??? means "not yet implemented".

scala> reorder(Seq(6.0,2.0,8.0,4.0), Seq(20,10,40,30))  // Test with type parameter A = Double.
res0: Seq[Double] = List(2.0, 6.0, 4.0, 8.0)
\end{lstlisting}


\subsubsection{Exercise \label{tuples-Exercise-5}\ref{tuples-Exercise-5}}

Given \lstinline!p:Seq[String]! and \lstinline!q:Seq[Int]! of equal
length and assuming that values in \lstinline!q! do not repeat, compute
a \lstinline!Map[Int, String]! mapping numbers from \lstinline!q!
to the corresponding strings from \lstinline!p!.

\subsubsection{Exercise \label{tuples-Exercise-6}\ref{tuples-Exercise-6}}

Write the solution of Exercise~\ref{tuples-Exercise-5} as a function
with type parameters \lstinline!P! and \lstinline!Q! instead of
the fixed types \lstinline!String! and \lstinline!Int!. Test it
with \lstinline!P = Boolean! and \lstinline!Q = Set[Int]!.

\subsubsection{Exercise \label{tuples-Exercise-9}\ref{tuples-Exercise-9}}

Given a \lstinline!Seq[(String, Int)]! showing a list of purchased
items (where item names may repeat), compute a \lstinline!Map[String, Int]!
showing the total counts: e.g., for the input 
\begin{lstlisting}
Seq(("apple", 2), ("pear", 3), ("apple", 5), ("lemon", 2), ("apple", 3))
\end{lstlisting}
the output must be \lstinline!Map("apple" -> 10, "pear" -> 3, "lemon" -> 2)!.

Hint: use \lstinline!groupBy!, \lstinline!map!, \lstinline!sum!.

\subsubsection{Exercise \label{tuples-Exercise-10}\ref{tuples-Exercise-10}}

Given a \lstinline!Seq[List[Int]]!, compute a new \lstinline!Seq[List[Int]]!
where each inner list contains \emph{three} largest elements from
the initial inner list (or fewer than three if the initial inner list
is shorter).

Hint: use \lstinline!map!, \lstinline!sortBy!, \lstinline!take!.

\subsubsection{Exercise \label{tuples-Exercise-11}\ref{tuples-Exercise-11}}

\textbf{(a)} Given two sets, \lstinline!p: Set[Int]! and \lstinline!q: Set[Int]!,
compute a set of type \lstinline!Set[(Int, Int)]! as the Cartesian
product of the sets \lstinline!p! and \lstinline!q!; that is, the
set of all pairs \lstinline!(x, y)! where \lstinline!x! is an element
from the set \lstinline!p! and \lstinline!y! is an element from
the set \lstinline!q!. 

\textbf{(b)} Implement this computation as a function with type parameters
\lstinline!I!, \lstinline!J! instead of \lstinline!Int!. The required
type signature and a sample test:
\begin{lstlisting}
def cartesian[I,J](p: Set[I], q: Set[J]): Set[(I, J)] = ???

scala> cartesian(Set("a", "b"), Set(10, 20))
res0: Set[(String, Int)] = Set((a,10), (a,20), (b,10), (b,20))
\end{lstlisting}

Hint: use \lstinline!flatMap! and \lstinline!map! on sets.

\subsubsection{Exercise \label{tuples-Exercise-12}\ref{tuples-Exercise-12}{*}}

Given a \lstinline!Seq[Map[Person, Amount]]!, showing the amounts
various people paid on each day, compute a \lstinline!Map[Person, Seq[Amount]]!,
showing the sequence of payments for each person. Assume that \lstinline!Person!
and \lstinline!Amount! are type parameters. The required type signature
and a sample test:
\begin{lstlisting}[mathescape=true]
def payments[Person, Amount](data: Seq[Map[Person, Amount]]): Map[Person, Seq[Amount]] = ???
// On day 1, Tarski paid 10 and G$\text{\color{dkgreen}\"o}$del paid 20. On day 2, Church paid 100 and Gentzen paid 50, etc.
scala> payments(Seq(Map("Tarski" -> 10, "G$\text{\color{mauve}\"o}$del" -> 20), Map("Church" -> 100, "Gentzen" -> 50), Map("Tarski" -> 50), Map("Banach" -> 15, "Gentzen" -> 35)))
res0: Map[String, Seq[Int]] = Map(Genzten -> List(50, 35), Church -> List(100), Banach -> List(15), Tarski -> List(10, 50), G$\text{\"o}$del -> List(20))
\end{lstlisting}

Hint: use \lstinline!flatMap!, \lstinline!groupBy!, \lstinline!mapValues!
on dictionaries.

\section{Converting a sequence into a single value}

Until this point, we have been working with sequences using methods
such as \lstinline!map! and \lstinline!zip!. These techniques are
powerful but still insufficient for solving certain problems.

A simple computation that is impossible to do using \lstinline!map!
is obtaining the sum of a sequence of numbers. The standard library
method \lstinline!sum! already does this; but we cannot re-implement
\lstinline!sum! ourselves by using \lstinline!map!, \lstinline!zip!,
or \lstinline!filter!. These operations always compute \emph{new}
\emph{sequences}, while we need to compute a single value (the sum
of all elements) from a sequence. 

We have seen a few library methods such as \lstinline!count!, \lstinline!length!,
and \lstinline!max! that compute a single value from a sequence;
but we still cannot implement \lstinline!sum! using these methods.
What we need is a more general way of converting a sequence to a single
value, such that we could ourselves implement \lstinline!sum!, \lstinline!count!,
\lstinline!max!, and other similar computations.

Another task not solvable with \lstinline!map!, \lstinline!sum!,
etc., is to compute a floating-point number from a given sequence
of decimal digits (including a \textsf{``}dot\textsf{''} character):
\begin{lstlisting}
def digitsToDouble(ds: Seq[Char]): Double = ???

scala> digitsToDouble(Seq('2', '0', '4', '.', '5'))
res0: Double = 204.5
\end{lstlisting}
Why is it impossible to implement this function using \lstinline!map!,
\lstinline!sum!, and other methods we have seen so far? In fact,
the same task for \emph{integer} numbers (instead of floating-point
numbers) can be implemented via \lstinline!length!, \lstinline!map!,
\lstinline!sum!, and \lstinline!zip!:
\begin{lstlisting}
def digitsToInt(ds: Seq[Int]): Int = {
  val n = ds.length
  // Compute a sequence of powers of 10, e.g., [1000, 100, 10, 1].
  val powers: Seq[Int] = (0 to n - 1).map(k => math.pow(10, n - 1 - k).toInt)
  // Sum the powers of 10 with coefficients from `ds`.
  (ds zip powers).map { case (d, p) => d * p }.sum                                  
}

scala> digitsToInt(Seq(2,4,0,5))
res0: Int = 2405
\end{lstlisting}
This task is doable because the required computation can be written
as the formula
\[
r=\sum_{k=0}^{n-1}d_{k}*10^{n-1-k}\quad.
\]
The sequence of powers of $10$ can be computed separately and \textsf{``}zipped\textsf{''}
with the sequence of digits $d_{k}$. However, for floating-point
numbers, the sequence of powers of $10$ depends on the position of
the \textsf{``}dot\textsf{''} character. Methods such as \lstinline!map! or \lstinline!zip!
cannot compute a sequence whose next elements depend on previous elements,
where the dependence is described by some custom function.

\subsection{Inductive definitions of aggregation functions\label{subsec:Inductive-definitions-of-aggregation-functions}}

\textbf{Mathematical induction\index{mathematical induction}} is
a general way of expressing the dependence of next values on previously
computed values. To define a function from a sequence to a single
value (e.g., an aggregation function \lstinline!f: Seq[Int] => Int!)
via mathematical induction, we need to specify two computations:
\begin{itemize}
\item (\textbf{\index{mathematical induction!base case}}The \textbf{base
case} of the induction.) We need to specify what value the function
\lstinline!f! returns for an empty sequence, \lstinline!Seq()!.
The standard method \lstinline!isEmpty! can be used to detect empty
sequences. In case the function \lstinline!f! is only defined for
non-empty sequences, we need to specify what the function \lstinline!f!
returns for a one-element sequence such as \lstinline!Seq(x)!, with
any \lstinline!x!.
\item (\textbf{\index{mathematical induction!inductive step}}The \textbf{inductive
step}.) Assuming that the function \lstinline!f! is already computed
for some sequence \lstinline!xs! (the \textbf{\index{mathematical induction!inductive assumption}inductive
assumption}), how to compute the function \lstinline!f! for a sequence
with one more element \lstinline!x!? The sequence with one more element
is written as \lstinline!xs :+ x!. So, we need to specify how to
compute \lstinline!f(xs :+ x)! assuming that \lstinline!f(xs)! is
already known.
\end{itemize}
Once these two computations are specified, the function \lstinline!f!
is defined (and can in principle be computed) for an arbitrary input
sequence. This is how induction works in mathematics, and it works
in the same way in functional programming. With this approach, the
inductive definition of the method \lstinline!sum! looks like this:
\begin{itemize}
\item The sum of an empty sequence is $0$. That is, \lstinline!Seq().sum == 0!.
\item If the result \lstinline!xs.sum! is already known for a sequence
\lstinline!xs!, and we have a sequence that has one more element
\lstinline!x!, the new result is equal to \lstinline!xs.sum + x!.
In code, this is \lstinline!(xs :+ x).sum == xs.sum + x!.
\end{itemize}
The inductive definition of the function \lstinline!digitsToInt!
is:
\begin{itemize}
\item For an empty sequence of digits, \lstinline!Seq()!, the result is
\lstinline!0!. This is a convenient base case, even if we never call
\lstinline!digitsToInt! on an empty sequence.
\item If \lstinline!digitsToInt(xs)! is already known for a sequence \lstinline!xs!
of digits, and we have a sequence \lstinline!xs :+ x! with one more
digit \lstinline!x!, then
\begin{lstlisting}
digitsToInt(xs :+ x) = digitsToInt(xs) * 10 + x
\end{lstlisting}
\end{itemize}
Let us write inductive definitions for methods such as \lstinline!length!,
\lstinline!max!, and \lstinline!count!:
\begin{itemize}
\item The length of a sequence:
\begin{itemize}
\item for an empty sequence, \lstinline!Seq().length == 0!
\item if \lstinline!xs.length! is known then \lstinline!(xs :+ x).length == xs.length + 1!
\end{itemize}
\item Maximum element of a sequence (undefined for empty sequences):
\begin{itemize}
\item for a one-element sequence, \lstinline!Seq(x).max == x! 
\item if \lstinline!xs.max! is known then \lstinline!(xs :+ x).max == math.max(xs.max, x)!
\end{itemize}
\item Count the sequence elements satisfying a predicate \lstinline!p!:
\begin{itemize}
\item for an empty sequence, \lstinline!Seq().count(p) == 0!
\item if \lstinline!xs.count(p)! is known then \lstinline!(xs :+ x).count(p) == xs.count(p) + c!,
where we set \lstinline!c = 1! when \lstinline!p(x) == true! and
\lstinline!c = 0! otherwise
\end{itemize}
\end{itemize}
There are two main ways of translating mathematical induction into
code. The first way is to write a recursive function. The second way
is to use a standard library function, such as \lstinline!foldLeft!
or \lstinline!reduce!. Most often it is better to use the standard
library functions, but sometimes the code is more transparent when
using explicit recursion. So let us consider each of these ways in
turn.

\subsection{Implementing functions by recursion}

A \textbf{recursive function\index{recursive function}} is any function
that calls itself somewhere within its own body. The call to itself
is the \textbf{recursive call}.

When the body of a recursive function is evaluated, it may repeatedly
call itself with different arguments until the result value can be
computed \emph{without} any recursive calls. The last recursive call
corresponds to the base case of the induction. It is an error if the
base case is never reached, as in this example:
\begin{lstlisting}
scala> def infiniteLoop(x: Int): Int = infiniteLoop(x+1)
infiniteLoop: (x: Int)Int

scala> infiniteLoop(2) // You will need to press Ctrl-C to stop this.
\end{lstlisting}

We translate mathematical induction into code by first writing a condition
to decide whether we have the base case or the inductive step. As
an example, let us define \lstinline!sum! by recursion. The base
case returns \lstinline!0!, and the inductive step returns a value
computed from the recursive call. In this case, 

\begin{wrapfigure}{l}{0.53\columnwidth}%
\vspace{-0.85\baselineskip}
\begin{lstlisting}
def sum(s: Seq[Int]): Int = if (s.isEmpty) 0 else {
  val x = s.head  // To split s = x +: xs, compute x
  val xs = s.tail // and xs.
  sum(xs) + x     // Call sum(...) recursively.
}
\end{lstlisting}

\vspace{-1.5\baselineskip}
\end{wrapfigure}%

\noindent In this example, the \lstinline!if/else! expression will
separate the base case from the inductive step. In the inductive step,
it is convenient to split the given sequence \lstinline!s! into its
first element \lstinline!x!, or the \textsf{``}head\textsf{''} of \lstinline!s!,
and the remainder (\textsf{``}tail\textsf{''}) sequence \lstinline!xs!. So, we split
\lstinline!s! as \lstinline!s = x +: xs! rather than as \lstinline!s = xs :+ x!.\footnote{It is easier to remember the meaning of \lstinline!x +: xs! and \lstinline!xs :+ x!
if we note that the \emph{col}on (\lstinline!:!) always points to
the \emph{col}lection (\lstinline!xs!) and the plus (\lstinline!+!)
to a single element (\lstinline!x!) that is being added.}

For computing the sum of a numerical sequence, the order of summation
does not matter. However, the order of operations \emph{will} matter
for many other computational tasks. We need to choose whether the
inductive step should split the sequence as \lstinline!s = x +: xs!
or as \lstinline!s = xs :+ x!, depending on the task at hand.

Consider the implementation of \lstinline!digitsToInt! according
to the inductive definition shown in the previous subsection:

\begin{wrapfigure}{l}{0.64\columnwidth}%
\vspace{-0.85\baselineskip}
\begin{lstlisting}
def digitsToInt(s: Seq[Int]): Int = if (s.isEmpty) 0 else {
  val x = s.last             // To split s = xs :+ x, compute x
  val xs = s.take(s.length - 1)  // and xs.
  digitsToInt(xs) * 10 + x // Call digitstoInt(...) recursively.
}
\end{lstlisting}

\vspace{-1.5\baselineskip}
\end{wrapfigure}%

\noindent In this example, it is important to split the sequence \lstinline!s!
into \lstinline!xs :+ x! and not into \lstinline!x +: xs!. The reason
is that digits increase their numerical value from right to left,
so the correct result is computed if we split \lstinline!s! into
\lstinline!xs :+ x! and multiply \lstinline!digitsToInt(xs)! by
$10$.

These examples show how mathematical induction is converted into recursive
code. This approach often works but has two technical problems. The
first problem is that the code will fail due to a stack overflow when
the input sequence \lstinline!s! is long enough. In the next subsection,
we will see how this problem is solved (at least in some cases) using
tail recursion. 

The second problem is that each inductively defined function repeats
the code for checking the base case and the code for splitting the
sequence \lstinline!s! into the subsequence \lstinline!xs! and the
extra element \lstinline!x!. This repeated common code can be put
into a library function, and the Scala library provides such functions.
We will look at using them in Section~\ref{subsec:implementing-general-aggregation-foldleft}.

\subsection{Tail recursion\label{subsec:Tail-recursion}}

The code of \lstinline!lengthS! will fail for large enough sequences.
To see why, consider an inductive definition of the \lstinline!length!
method as a function \lstinline!lengthS!:
\begin{lstlisting}
def lengthS(s: Seq[Int]): Int =
  if (s.isEmpty) 0
  else 1 + lengthS(s.tail)

scala> lengthS((1 to 1000).toList)
res0: Int = 1000

scala> val s = (1 to 100000).toList
s: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, ...

scala> lengthS(s)
java.lang.StackOverflowError
  at .lengthS(<console>:12)
  at .lengthS(<console>:12)
  at .lengthS(<console>:12)
...
\end{lstlisting}
The problem is not due to insufficient main memory: we \emph{are}
able to compute and hold in memory the entire sequence \lstinline!s!.
The problem is with the code of the function \lstinline!lengthS!.
This function calls itself \emph{inside} the expression \lstinline!1 + lengthS(...)!.
So we can visualize how the computer evaluates this code:

\begin{wrapfigure}{l}{0.37\columnwidth}%
\vspace{-1\baselineskip}
\begin{lstlisting}
lengthS(Seq(1, 2, ..., 100000))
  = 1 + lengthS(Seq(2, ..., 100000))
  = 1 + (1 + lengthS(Seq(3, ..., 100000)))
  = ...
\end{lstlisting}

\vspace{-1.5\baselineskip}
\end{wrapfigure}%

\noindent The function body of \lstinline!lengthS! will evaluate
the inductive step, that is, the \textsf{``}\lstinline!else!\textsf{''} part of the
\textsf{``}\lstinline!if/else!\textsf{''}, about $100,000$ times. Each time, the
sub-expression with nested computations \lstinline!1+(1+(...))! will
get larger. This intermediate sub-expression needs to be held somewhere
in memory, until at some point the function body goes into the base
case and returns a value. When that happens, the entire intermediate
sub-expression will contain about $100,000$ nested function calls
still waiting to be evaluated. This sub-expression is held in a special
area of memory called \textbf{\index{stack memory}stack memory},
where the not-yet-evaluated nested function calls are held in the
order of their calls on a stack. Due to the way computer memory is
managed, the stack memory has a fixed size and cannot grow automatically.
So, when the intermediate expression becomes large enough, it causes
an overflow of the stack memory and crashes the program.

One way to avoid stack overflows is to use a trick called \textbf{tail
recursion\index{tail recursion}}. Using tail recursion means rewriting
the code so that all recursive calls occur at the end positions (at
the \textsf{``}tails\textsf{''}) of the function body. In other words, each recursive
call must be \emph{itself} the last computation in the function body,
rather than placed inside other computations. Here is an example of
tail-recursive code:

\begin{wrapfigure}{l}{0.42\columnwidth}%
\vspace{-1.1\baselineskip}
\begin{lstlisting}
def lengthT(s: Seq[Int], res: Int): Int =
  if (s.isEmpty) res
  else lengthT(s.tail, res + 1)
\end{lstlisting}

\vspace{-1.5\baselineskip}
\end{wrapfigure}%

\noindent In this code, one of the branches of the \lstinline!if/else!
returns a fixed value without doing any recursive calls, while the
other branch returns the result of a recursive call to \lstinline!lengthT(...)!.
In the code of \lstinline!lengthT!, recursive calls never occur within
any sub-expressions.

It is not a problem that the recursive call to \lstinline!lengthT!
has some sub-expressions such as \lstinline!res + 1! as its arguments,
because all these sub-expressions will be computed \emph{before} \lstinline!lengthT!
is recursively called. The recursive call to \lstinline!lengthT!
is the \emph{last} computation performed by this branch of the \lstinline!if/else!.
A tail-recursive function can have many \lstinline!if/else! or \lstinline!match/case!
branches, with or without recursive calls; but all recursive calls
must be always the last expressions returned.

The Scala compiler has a feature for checking automatically that a
function\textsf{'}s code is tail-recursive: the \lstinline!@tailrec! annotation.
If a function with a \lstinline!@tailrec! annotation is not tail-recursive,
or is not recursive at all, the program will not compile.
\begin{lstlisting}
@tailrec def lengthT(s: Seq[Int], res: Int): Int = 
  if (s.isEmpty) res
  else lengthT(s.tail, res + 1)
\end{lstlisting}
Let us trace the evaluation of this function on an example:

\begin{wrapfigure}{l}{0.565\columnwidth}%
\vspace{-0.8\baselineskip}
\begin{lstlisting}
lengthT(Seq(1, 2, 3), 0)
  = lengthT(Seq(2, 3), 0 + 1) // = lengthT(Seq(2, 3), 1)
  = lengthT(Seq(3), 1 + 1)    // = lengthT(Seq(3), 2)
  = lengthT(Seq(), 2 + 1)     // = lengthT(Seq(), 3)
  = 3
\end{lstlisting}

\vspace{-1.5\baselineskip}
\end{wrapfigure}%

\noindent All sub-expressions such as \lstinline!1 + 1! and \lstinline!2 + 1!
are computed \emph{before} recursive calls to \lstinline!lengthT!.
Because of that, sub-expressions do not grow within the stack memory.
This is the main benefit of tail recursion.

How did we rewrite the code of \lstinline!lengthS! into the tail-recursive
code of \lstinline!lengthT!? An important difference between \lstinline!lengthS!
and \lstinline!lengthT! is the additional argument, \lstinline!res!,
called the \textbf{accumulator}\index{accumulator argument}\index{recursive function!accumulator argument}
\textbf{argument}. This argument is equal to an intermediate result
of the computation. The next intermediate result (\lstinline!res + 1!)
is computed and passed on to the next recursive call via the accumulator
argument. In the base case of the recursion, the function now returns
the accumulated result, \lstinline!res!, rather than \lstinline!0!,
because at that time the computation is finished.

Rewriting code by adding an accumulator argument to achieve tail recursion
is called the \textbf{accumulator technique} or the \textsf{``}accumulator
trick\textsf{''}.

One consequence of using the accumulator trick is that the function
\lstinline!lengthT! now always needs a value for the accumulator
argument. However, our goal is to implement a function such as \lstinline!length(s)!
with just one argument, \lstinline!s: Seq[Int]!. We can define \lstinline!length(s) = lengthT(s, ???)!
if we supply an initial accumulator value. The correct initial value
for the accumulator is \lstinline!0!, since in the base case (an
empty sequence \lstinline!s!) we need to return \lstinline!0!.

So, a tail-recursive implementation of \lstinline!lengthT! requires
us to define \emph{two} functions: the tail-recursive \lstinline!lengthT!
and the main function that will set the initial value of the accumulator
argument. To emphasize that \lstinline!lengthT! is a helper function,
one could define it \emph{inside} the main function:
\begin{lstlisting}
def length[A](xs: Seq[A]): Int = {
  @tailrec def lengthT(s: Seq[A], res: Int): Int = {
    if (s.isEmpty) res
    else lengthT(s.tail, res + 1)
  }
  lengthT(xs, 0)
}
\end{lstlisting}
When \lstinline!length! is implemented like that, users will not
be able to call \lstinline!lengthT! directly, because \lstinline!lengthT!
is only visible within the body of the \lstinline!length! function.

Another possibility in Scala is to use a \textbf{default value\index{default value}}
for the \lstinline!res! argument:
\begin{lstlisting}
@tailrec def length[A](s: Seq[A], res: Int = 0): Int = 
  if (s.isEmpty) res
  else length(s.tail, res + 1)
\end{lstlisting}
Giving a default value for a function argument is the same as defining
\emph{two} functions: one with that argument and one without. For
example, the syntax
\begin{lstlisting}
def f(x: Int, y: Boolean = false): Int = ... // Function body.
\end{lstlisting}
is equivalent to defining two functions (with the same name):
\begin{lstlisting}
def f(x: Int, y: Boolean) = ...     // Define the function body here.
def f(x: Int): Int = f(Int, false)  // Call the function defined above.
\end{lstlisting}
Using a default argument, we can define the tail-recursive helper
function and the main function at once, making the code shorter.

The accumulator trick works in a large number of cases, but it may
be far from obvious how to introduce the accumulator argument, what
its initial value must be, and how to define the inductive step for
the accumulator. In the example with the \lstinline!lengthT! function,
the accumulator trick works because of the special mathematical property
of the expression being computed:
\[
1+\left(1+\left(1+\left(...+0\right)\right)\right)=\left(\left(\left(0+1\right)+1\right)+...\right)+1\quad.
\]
This equation follows from the \textbf{\index{associativity law!of addition}associativity
law} of addition. So, the computation can be rearranged to group all
additions to the left. In code, it means that intermediate expressions
are computed immediately before making recursive calls; this avoids
the growth of the intermediate expressions. 

Usually, the accumulator trick works because some associativity law
is present. In that case, we are able to rearrange the order of recursive
calls so that these calls always occur outside all other sub-expressions
\textemdash{} that is, in tail positions. However, not all computations
obey a suitable associativity law. Even if a code rearrangement exists,
it may not be immediately obvious how to find it.

As an example, consider a tail-recursive re-implementation of the
function \lstinline!digitsToInt! from the previous subsection, where
the recursive call is within a sub-expression \lstinline!digitsToInt(xs) * 10 + x!.
To transform the code into a tail-recursive form, we need to rearrange
the main computation,
\[
r=d_{n-1}+10*\left(d_{n-2}+10*\left(d_{n-3}+10*\left(...+10*d_{0}\right)\right)\right)\quad,
\]
so that the operations group to the left. We can do this by rewriting
$r$ as
\[
r=\left(\left(d_{0}*10+d_{1}\right)*10+...\right)*10+d_{n-1}\quad.
\]
It follows that the digit sequence \lstinline!s! must be split into
the \emph{leftmost} digit and the rest, \lstinline!s == s.head +: s.tail!.
So, a tail-recursive implementation of the above formula is

\begin{wrapfigure}{l}{0.57\columnwidth}%
\vspace{-0.95\baselineskip}
\begin{lstlisting}
@tailrec def fromDigits(s: Seq[Int], res: Int = 0):Int =
  // `res` is the accumulator.
  if (s.isEmpty) res
  else fromDigits(s.tail, 10 * res + s.head)
\end{lstlisting}

\vspace{-1.5\baselineskip}
\end{wrapfigure}%

\noindent Despite a certain similarity between this code and the code
of \lstinline!digitsToInt! from the previous subsection, the implementation
\lstinline!fromDigits! cannot be directly derived from the inductive
definition of \lstinline!digitsToInt!. One needs a separate proof
that \lstinline!fromDigits(s, 0)! computes the same result as \lstinline!digitsToInt(s)!.
This holds due to the following property:

\subsubsection{Statement \label{subsec:Statement-fromdigitsT-equals-fromdigits}\ref{subsec:Statement-fromdigitsT-equals-fromdigits}}

For any \lstinline!s: Seq[Int]! and \lstinline!r: Int!, we have
\begin{lstlisting}
fromDigits(s, r) = digitsToInt(s) + r * math.pow(10, s.length)
\end{lstlisting}


\subparagraph{Proof}

We prove this by induction. To shorten the proof, denote sequences
by $\left[1,2,3\right]$ instead of \lstinline!Seq(1, 2, 3)! and
temporarily write $d(s)$ instead of \lstinline!digitsToInt(s)! and
$f(s,r)$ instead of \lstinline!fromDigitsT(s, r)!. Then an inductive
definition of $f(s,r)$ is
\begin{equation}
f([],r)=r\quad,\quad\quad f([x]\pplus s,r)=f(s,10*r+x)\quad.\label{eq:stmt-fromdigitsT-expand-f}
\end{equation}
Denoting the length of a sequence $s$ by $\left|s\right|$, we reformulate
Statement~\ref{subsec:Statement-fromdigitsT-equals-fromdigits} as
\begin{equation}
f(s,r)=d(s)+r*10^{\left|s\right|}\quad.\label{eq:stmt-fromdigitsT-reformulated}
\end{equation}

We prove Eq.~(\ref{eq:stmt-fromdigitsT-reformulated}) by induction.
For the base case $s=\left[\right]$, we have $f(\left[\right],r)=r$
and $d(\left[\right])+r*10^{0}=r$ since $d(\left[\right])=0$ and
$\left|s\right|=0$. The resulting equality $r=r$ proves the base
case. 

To prove the inductive step, we assume that Eq.~(\ref{eq:stmt-fromdigitsT-reformulated})
holds for a given sequence $s$; then we need to prove that
\begin{equation}
f([x]\pplus s,r)=d([x]\pplus s)+r*10^{\left|s\right|+1}\quad.\label{eq:stmt-need-to-prove-step}
\end{equation}
We will transform the left-hand side and the right-hand side separately,
hoping to obtain the same expression. The left-hand side of Eq.~(\ref{eq:stmt-need-to-prove-step}):
\begin{align*}
 & f([x]\pplus s,r)\\
{\color{greenunder}\text{use Eq.~(\ref{eq:stmt-fromdigitsT-expand-f})}:}\quad & =f(s,10*r+x)\\
{\color{greenunder}\text{use Eq.~(\ref{eq:stmt-fromdigitsT-reformulated})}:}\quad & =d(s)+\left(10*r+x\right)*10^{\left|s\right|}\quad.
\end{align*}
The right-hand side of Eq.~(\ref{eq:stmt-need-to-prove-step}) contains
$d([x]\pplus s)$, which we somehow need to simplify. Assuming that
$d(s)$ correctly calculates a number from its digits, we use a property
of decimal notation: a digit $x$ in front of $n$ other digits has
the value $x*10^{n}$. This property can be formulated as an equation,
\begin{equation}
d([x]\pplus s)=x*10^{\left|s\right|}+d(s)\quad.\label{stmt-from-digits-property}
\end{equation}
So, the right-hand side of Eq.~(\ref{eq:stmt-need-to-prove-step})
can be rewritten as
\begin{align*}
 & d([x]\pplus s)+r*10^{\left|s\right|+1}\\
{\color{greenunder}\text{use Eq.~(\ref{stmt-from-digits-property})}:}\quad & =x*10^{\left|s\right|}+d(s)+r*10^{\left|s\right|+1}\\
{\color{greenunder}\text{factor out }10^{\left|s\right|}:}\quad & =d(s)+\left(10*r+x\right)*10^{\left|s\right|}\quad.
\end{align*}
We have successfully transformed both sides of Eq.~(\ref{eq:stmt-need-to-prove-step})
to the same expression.

We have not yet proved that the function $d$ satisfies the property
in Eq.~(\ref{stmt-from-digits-property}). The proof uses induction
and begins by writing the code of $d$ in a short notation,
\begin{equation}
d(\left[\right])=0\quad,\quad\quad d(s\pplus[y])=d(s)*10+y\quad.\label{eq:stmt-fromdigits-code-of-d}
\end{equation}
The base case is Eq.~(\ref{stmt-from-digits-property}) with $s=[]$.
It is proved by
\[
x=d([]\pplus[x])=d([x]\pplus[])=x*10^{0}+d(\left[\right])=x\quad.
\]
The inductive step assumes Eq.~(\ref{stmt-from-digits-property})
for a given $x$ and a given sequence $s$, and needs to prove that
for any $y$, the same property holds with $s\negmedspace+\negthickspace+[y]$
instead of $s$:
\begin{equation}
d([x]\pplus s\pplus[y])=x*10^{\left|s\right|+1}+d(s\pplus[y])\quad.\label{eq:stmt-from-digits-induction-step}
\end{equation}
The left-hand side of Eq.~(\ref{eq:stmt-from-digits-induction-step})
is transformed into its right-hand side like this:
\begin{align*}
 & d([x]\pplus s\pplus[y])\\
{\color{greenunder}\text{use Eq.~(\ref{eq:stmt-fromdigits-code-of-d})}:}\quad & =d([x]\pplus s)*10+y\\
{\color{greenunder}\text{use Eq.~(\ref{stmt-from-digits-property})}:}\quad & =(x*10^{\left|s\right|}+d(s))*10+y\\
{\color{greenunder}\text{expand parentheses}:}\quad & =x*10^{\left|s\right|+1}+d(s)*10+y\\
{\color{greenunder}\text{use Eq.~(\ref{eq:stmt-fromdigits-code-of-d})}:}\quad & =x*10^{\left|s\right|+1}+d(s\pplus[y])\quad.
\end{align*}
This demonstrates Eq.~(\ref{eq:stmt-from-digits-induction-step})
and so concludes the proof.

\subsection{Implementing general aggregation (\texttt{foldLeft})\label{subsec:implementing-general-aggregation-foldleft}}

An \textbf{aggregation}\index{aggregation} converts a sequence of
values into a single value. In general, the type of the result may
be different from the type of sequence elements. To describe that
general situation, we introduce type parameters, \lstinline!A! and
\lstinline!B!, so that the input sequence is of type \lstinline!Seq[A]!
and the aggregated value is of type \lstinline!B!. Then an inductive
definition of any aggregation function \lstinline!f: Seq[A] => B!
looks like this:
\begin{itemize}
\item (Base case.) For an empty sequence, we have \lstinline!f(Seq()) = b0!,
where \lstinline!b0: B! is a given value.
\item (Inductive step.) Assuming that \lstinline!f(xs) = b! is already
computed, we define \lstinline!f(xs :+ x) = g(x, b)! where \lstinline!g!
is a given function with type signature \lstinline!g: (A, B) => B!.
\end{itemize}
The code implementing \lstinline!f! is written using recursion:
\begin{lstlisting}
def f[A, B](s: Seq[A]): B =
  if (s.isEmpty) b0
  else g(s.last, f(s.take(s.length - 1)))
\end{lstlisting}
We can now refactor this code into a generic utility function, by
making \lstinline!b0! and \lstinline!g! into parameters. A possible
implementation is
\begin{lstlisting}
def f[A, B](s: Seq[A], b: B, g: (A, B) => B): B =
  if (s.isEmpty) b
  else g(s.last, f(s.take(s.length - 1), b, g)
\end{lstlisting}
However, this implementation is not tail-recursive. Applying \lstinline!f!
to a sequence of, say, three elements, \lstinline!Seq(x, y, z)!,
will create an intermediate expression \lstinline!g(z, g(y, g(x, b)))!.
This expression will grow with the length of \lstinline!s!, which
is not acceptable. To rearrange the computation into a tail-recursive
form, we need to start the base case at the innermost call \lstinline!g(x, b)!,
then compute \lstinline!g(y, g(x, b))! and continue. In other words,
we need to traverse the sequence starting from its \emph{leftmost}
element \lstinline!x!, rather than starting from the right. So, instead
of splitting the sequence \lstinline!s! into \lstinline!s.take(s.length - 1) :+ s.last!
as we did in the code of \lstinline!f!, we need to split \lstinline!s!
into \lstinline!s.head +: s.tail!. Let us also exchange the order
of the arguments of \lstinline!g!, in order to be more consistent
with the way this code is implemented in the Scala library. The resulting
code is tail-recursive:
\begin{lstlisting}
@tailrec def leftFold[A, B](s: Seq[A], b: B, g: (B, A) => B): B =
  if (s.isEmpty) b
  else leftFold(s.tail, g(b, s.head), g)
\end{lstlisting}
We call this function a \textsf{``}left fold\textsf{''} because it aggregates (or
\textsf{``}folds\textsf{''}) the sequence starting from the leftmost element.

In this way, we have defined a general method of computing any inductively
defined aggregation function on a sequence. The function \lstinline!leftFold!
implements the logic of aggregation\index{aggregation} defined via
mathematical induction. Using \lstinline!leftFold!, we can write
concise implementations of methods such as \lstinline!sum!, \lstinline!max!,
and many other aggregation functions. The method \lstinline!leftFold!
already contains all the code necessary to set up the base case and
the inductive step. The programmer just needs to specify the expressions
for the initial value \lstinline!b! and for the updater function
\lstinline!g!.

As a first example, let us use \lstinline!leftFold! for implementing
the \lstinline!sum! method:
\begin{lstlisting}
def sum(s: Seq[Int]): Int = leftFold(s, 0, (x, y) => x + y )
\end{lstlisting}
To understand in detail how \lstinline!leftFold! works, let us trace
the evaluation of this function when applied to \lstinline!Seq(1, 2, 3)!:
\begin{lstlisting}
sum(Seq(1, 2, 3)) == leftFold(Seq(1, 2, 3), 0, g)
                     // Here, g = (x, y) => x + y, so g(x, y) = x + y.
  == leftFold(Seq(2, 3), g(0, 1), g)                  // g (0, 1) = 1.
  == leftFold(Seq(2, 3), 1, g)   // Now expand the code of `leftFold`.
  == leftFold(Seq(3), g(1, 2), g)     // g(1, 2) = 3; expand the code.
  == leftFold(Seq(), g(3, 3), g)      // g(3, 3) = 6; expand the code.
  == 6
\end{lstlisting}
The second argument of \lstinline!leftFold! is the accumulator argument.
The initial value of the accumulator is specified when first calling
\lstinline!leftFold!. At each iteration, the new accumulator value
is computed by calling the updater function \lstinline!g!, which
uses the previous accumulator value and the value of the next sequence
element. To visualize the process of recursive evaluation, it is convenient
to write a table showing the sequence elements and the accumulator
values as they are updated:
\begin{center}
\begin{tabular}{|c|c|c|}
\hline 
\textbf{\small{}Current element }\lstinline!x! & \textbf{\small{}Old accumulator value} & \textbf{\small{}New accumulator value}\tabularnewline
\hline 
\hline 
{\small{}}\lstinline!1! & {\small{}}\lstinline!0! & {\small{}}\lstinline!1!\tabularnewline
\hline 
{\small{}}\lstinline!2! & {\small{}}\lstinline!1! & {\small{}}\lstinline!3!\tabularnewline
\hline 
{\small{}}\lstinline!3! & {\small{}}\lstinline!3! & {\small{}}\lstinline!6!\tabularnewline
\hline 
\end{tabular}
\par\end{center}

We implemented \lstinline!leftFold! only as an illustration. Scala\textsf{'}s
library has a method called \lstinline!foldLeft! implementing the
same logic using a slightly different type signature. To see this
difference, compare the implementation of \lstinline!sum! using our
\lstinline!leftFold! function and using the standard \lstinline!foldLeft!
method:
\begin{lstlisting}
def sum(s: Seq[Int]): Int = leftFold(s, 0, (x, y) => x + y )

def sum(s: Seq[Int]): Int = s.foldLeft(0) { (x, y) => x + y }
\end{lstlisting}
The syntax of \lstinline!foldLeft! makes it more convenient to use
a nameless function as the updater argument of \lstinline!foldLeft!,
since curly braces separate that argument from others. We will use
the standard \lstinline!foldLeft! method from now on.

In general, the type of the accumulator value can be different from
the type of the sequence elements. An example is an implementation
of \lstinline!count!:

\begin{wrapfigure}{l}{0.55\columnwidth}%
\vspace{-0.75\baselineskip}
\begin{lstlisting}
def count[A](s: Seq[A], p: A => Boolean): Int =
  s.foldLeft(0) { (x, y) => x + (if (p(y)) 1 else 0) }
\end{lstlisting}

\vspace{-0.9\baselineskip}
\end{wrapfigure}%

\noindent The accumulator is of type \lstinline!Int!, while the sequence
elements can have an arbitrary type, parameterized by \lstinline!A!.
The \lstinline!foldLeft! method works in the same way for all types
of accumulators and all types of sequence elements.

The method \lstinline!foldLeft! is available in the Scala library
for all collections, including dictionaries and sets. Since \lstinline!foldLeft!
is tail-recursive, no stack overflows will occur even for very large
sequences.

It is important to gain experience using the \lstinline!foldLeft!
method. The Scala library contains several other methods similar to
\lstinline!foldLeft!, such as \lstinline!foldRight! and \lstinline!reduce!.
In the following sections, we will mostly focus on \lstinline!foldLeft!.

\subsection{Solved examples: using \texttt{foldLeft}\index{solved examples}}

\subsubsection{Example \label{subsec:Example-1-max-foldleft}\ref{subsec:Example-1-max-foldleft}}

Use \lstinline!foldLeft! for implementing the \lstinline!max! function
for integer sequences. Return the special value \lstinline!Int.MinValue!
for empty sequences.

\subparagraph{Solution}

Begin by writing an inductive formulation of the \lstinline!max!
function for sequences. Base case: For an empty sequence, return \lstinline!Int.MinValue!.
Inductive step: If \lstinline!max! is already computed on a sequence
\lstinline!xs!, say \lstinline!max(xs) = b!, the value of \lstinline!max!
on a sequence \lstinline!xs :+ x! is \lstinline!math.max(b, x)!.
So, the code is:

\begin{lstlisting}
def max(s: Seq[Int]): Int = s.foldLeft(Int.MinValue) { (b, x) => math.max(b, x) }
\end{lstlisting}
If we are sure that the function will never be called on empty sequences,
we can implement \lstinline!max! in a simpler way by using the \lstinline!reduce!
method:
\begin{lstlisting}
def max(s: Seq[Int]): Int = s.reduce { (x, y) => math.max(x, y) }
\end{lstlisting}


\subsubsection{Example \label{subsec:Example-3-digitstoint-foldleft-1}\ref{subsec:Example-3-digitstoint-foldleft-1}}

For a given non-empty sequence \lstinline!xs: Seq[Double]!, compute
the minimum, the maximum, and the mean as a tuple $\left(x_{\min},x_{\max},x_{\text{mean}}\right)$.
The sequence should be traversed only once; i.e., the entire code
must be \lstinline!xs.foldLeft(...)!, using \lstinline!foldLeft!
only once.

\subparagraph{Solution}

Without the requirement of using a single traversal, we would write
\begin{lstlisting}
(xs.min, xs.max, xs.sum / xs.length)
\end{lstlisting}
However, this code traverses \lstinline!xs! at least three times,
since each of the aggregations \lstinline!xs.min!, \lstinline!xs.max!,
and \lstinline!xs.sum! iterates over \lstinline!xs!. We need to
combine the four inductive definitions of \lstinline!min!, \lstinline!max!,
\lstinline!sum!, and \lstinline!length! into a single inductive
definition of some function. What is the type of that function\textsf{'}s return
value? We need to accumulate intermediate values of \emph{all four}
numbers (\lstinline!min!, \lstinline!max!, \lstinline!sum!, and
\lstinline!length!) in a tuple. So the required type of the accumulator
is \lstinline!(Double, Double, Double, Double)!. To avoid repeating
a long type expression, we can define a type alias\index{type alias}
for it, say, \lstinline!D4!:
\begin{lstlisting}
scala> type D4 = (Double, Double, Double, Double)
defined type alias D4 
\end{lstlisting}
The updater updates each of the four numbers according to the definitions
of their inductive steps:
\begin{lstlisting}
def update(p: D4, x: Double): D4 = p match { case (min, max, sum, length) =>
   (math.min(x, min), math.max(x, max), x + sum, length + 1)
}
\end{lstlisting}
Now we can write the code of the required function:
\begin{lstlisting}
def f(xs: Seq[Double]): (Double, Double, Double) = {
  val init: D4 = (Double.PositiveInfinity, Double.NegativeInfinity, 0, 0)
  val (min, max, sum, length) = xs.foldLeft(init)(update)
  (min, max, sum/length)
}

scala> f(Seq(1.0, 1.5, 2.0, 2.5, 3.0))
res0: (Double, Double, Double) = (1.0,3.0,2.0)
\end{lstlisting}


\subsubsection{Example \label{subsec:Example-foldleft-6}\ref{subsec:Example-foldleft-6}}

Implement the \lstinline!map! method for sequences by using \lstinline!foldLeft!.
The input sequence should be of type \lstinline!Seq[A]! and the output
sequence of type \lstinline!Seq[B]!, where \lstinline!A! and \lstinline!B!
are type parameters. The required type signature of the function and
a sample test:
\begin{lstlisting}
def map[A, B](xs: Seq[A])(f: A => B): Seq[B] = ???

scala> map(List(1, 2, 3)) { x => x * 10 }
res0: Seq[Int] = List(10, 20, 30)
\end{lstlisting}


\subparagraph{Solution}

The required code should build a new sequence by applying the function
\lstinline!f! to each element. How can we build a new sequence using
\lstinline!foldLeft!? The evaluation of \lstinline!foldLeft! consists
of iterating over the input sequence and accumulating some result
value, which is updated at each iteration. Since the result of a \lstinline!foldLeft!
is always equal to the last computed accumulator value, it follows
that the new sequence should \emph{be} the accumulator value. So,
we need to update the accumulator by appending the value \lstinline!f(x)!,
where \lstinline!x! is the current element of the input sequence:
\begin{lstlisting}
def map[A, B](xs: Seq[A])(f: A => B): Seq[B] =
  xs.foldLeft(Seq[B]()) { (acc, x) => acc :+ f(x) }
\end{lstlisting}


\subsubsection{Example \label{subsec:Example-3-digitstoint-foldleft}\ref{subsec:Example-3-digitstoint-foldleft}}

Implement the function \lstinline!digitsToInt! using \lstinline!foldLeft!.

\subparagraph{Solution}

The inductive definition of \lstinline!digitsToInt! is directly translated
into code:

\begin{lstlisting}
def digitsToInt(d: Seq[Int]): Int =
  d.foldLeft(0){ (n, x) => n * 10 + x }
\end{lstlisting}


\subsubsection{Example \label{subsec:Example-4-digitstodouble-foldleft}\ref{subsec:Example-4-digitstodouble-foldleft}{*}}

Implement the function \lstinline!digitsToDouble! using \lstinline!foldLeft!.
The argument is of type \lstinline!Seq[Char]!. As a test, the expression
\lstinline!digitsToDouble(Seq('3','4','.','2','5'))! must evaluate
to \lstinline!34.25!. Assume that all input characters are either
digits or a dot (so, negative numbers are not supported).

\subparagraph{Solution}

The evaluation of a \lstinline!foldLeft! on a sequence of digits
will visit the sequence from left to right. The updating function
should work the same as in \lstinline!digitsToInt! until a dot character
is found. After that, we need to change the updating function. So,
we need to remember whether a dot character has been seen. The only
way for \lstinline!foldLeft! to \textsf{``}remember\textsf{''} any data is to hold
that data in the accumulator value. We can choose the type of the
accumulator according to our needs. So, for this task we can choose
the accumulator to be a \emph{tuple} that contains, for instance,
the floating-point result constructed so far and a \lstinline!Boolean!
flag showing whether we have already seen the dot character.

To see what \lstinline!digitsToDouble! must do, let us consider how
the evaluation of \lstinline!digitsToDouble(Seq('3', '4', '.', '2', '5'))!
should go. We can write a table showing the intermediate result at
each iteration. This will hopefully help us figure out what the accumulator
and the updater function $g(...)$ must be:
\begin{center}
\begin{tabular}{|c|c|c|}
\hline 
\textbf{\small{}Current digit $c$} & \textbf{\small{}Previous result $n$} & \textbf{\small{}New result $n'=g(n,c)$}\tabularnewline
\hline 
\hline 
\lstinline!'3'! & {\small{}$0.0$} & {\small{}$3.0$}\tabularnewline
\hline 
\lstinline!'4'! & {\small{}$3.0$} & {\small{}$34.0$}\tabularnewline
\hline 
\lstinline!'.'! & {\small{}$34.0$} & {\small{}$34.0$}\tabularnewline
\hline 
\lstinline!'2'! & {\small{}$34.0$} & {\small{}$34.2$}\tabularnewline
\hline 
\lstinline!'5'! & {\small{}$34.2$} & {\small{}$34.25$}\tabularnewline
\hline 
\end{tabular}
\par\end{center}

While the dot character was not yet seen, the updater function multiplies
the previous result by $10$ and adds the current digit. After the
dot character, the updater function must add to the previous result
the current digit divided by a factor that represents increasing powers
of $10$. In other words, the update computation $n'=g(n,c)$ must
be defined by:
\[
g(n,c)=\begin{cases}
n*10+c\quad, & \text{if the digit is before the dot character.}\\
n+c/f\quad, & \text{if after the dot character, where }f=10,100,1000,...\text{ for each new digit.}
\end{cases}
\]

The updater function $g$ has only two arguments: the current digit
and the previous accumulator value. So, the changing factor $f$ must
be \emph{part} \emph{of} the accumulator value, and must be multiplied
by $10$ at each digit after the dot. If the factor $f$ is not a
part of the accumulator value, the function $g$ will not have enough
information for computing the next accumulator value correctly. So,
the updater computation must be $n'=g(n,c,f)$, not $n'=g(n,c)$.

For this reason, we choose the accumulator type as a tuple \lstinline!(Double, Boolean, Double)!
where the first number is the result $n$ computed so far, the \lstinline!Boolean!
flag indicates whether the dot was already seen, and the third number
is $f$, that is, the power of $10$ by which the current digit will
be divided if the dot was already seen. Initially, the accumulator
tuple will be equal to \lstinline!(0.0, false, 10.0)!. Then the updater
function is implemented like this:
\begin{lstlisting}
def update(acc: (Double, Boolean, Double), c: Char): (Double, Boolean, Double) =
  acc match { case (num, flag, factor) =>
    if (c == '.') (num, true, factor) // Set flag to `true` after a dot character was seen.
    else {
      val digit = c - '0'
      if (flag) (num + digit / factor, flag, factor * 10) // This digit is after the dot.
      else (num * 10 + digit, flag, factor)               // This digit is before the dot.
    }
  }
\end{lstlisting}
Now we can implement \lstinline!digitsToDouble! as follows:

\begin{wrapfigure}{l}{0.48\columnwidth}%
\vspace{-0.5\baselineskip}
\begin{lstlisting}
def digitsToDouble(d: Seq[Char]): Double = {
  val initAcc = (0.0, false, 10.0)
  val (num, _, _) = d.foldLeft(initAcc)(update)
  num
}

scala> digitsToDouble(Seq('3','4','.','2','5'))
res0: Double = 34.25
\end{lstlisting}

\vspace{-1.2\baselineskip}
\end{wrapfigure}%

\noindent The result of calling \lstinline!d.foldLeft! is a tuple
\lstinline!(num, flag, factor)!, in which only the first part, \lstinline!num!,
is needed. In Scala\textsf{'}s pattern matching syntax, the underscore (\lstinline!_!)
denotes pattern variables whose values are not needed in the code.
We could get the first part using the accessor method \lstinline!._1!,
but the code will be more readable if we show all parts of the tuple
\lstinline!(num, _, _)!.

\subsubsection{Example \label{subsec:Example-foldleft-7}\ref{subsec:Example-foldleft-7}}

Implement a function \lstinline!toPairs! that converts a sequence
of type \lstinline!Seq[A]! to a sequence of pairs, \lstinline!Seq[(A, A)]!,
by putting together the adjacent elements pairwise. If the initial
sequence has an odd number of elements, a given default value of type
\lstinline!A! is used to fill the last pair. The required type signature
and an example test:
\begin{lstlisting}
def toPairs[A](xs: Seq[A], default: A): Seq[(A, A)] = ???

scala> toPairs(Seq(1, 2, 3, 4, 5, 6), -1)
res0: Seq[(Int, Int)] = List((1,2), (3,4), (5,6))

scala> toPairs(Seq("a", "b", "c"), "<nothing>")
res1: Seq[(String, String)] = List((a,b), (c,<nothing>)) 
\end{lstlisting}


\subparagraph{Solution}

We need to accumulate a sequence of pairs, and each pair needs two
values. However, we iterate over values in the input sequence one
by one. So, a new pair can be made only once every two iterations.
The accumulator needs to hold the information about the current iteration
being even or odd. For odd-numbered iterations, the accumulator also
needs to store the previous element that is still waiting for its
pair. Therefore, we choose the type of the accumulator to be a tuple
\lstinline!(Seq[(A, A)], Seq(A))!. The first sequence is the intermediate
result, and the second sequence is the \textsf{``}holdover\textsf{''}: it holds the
previous element for odd-numbered iterations and is empty for even-numbered
iterations. Initially, the accumulator should be empty. An example
evaluation is:
\begin{center}
\begin{tabular}{|c|c|c|}
\hline 
\textbf{\small{}Current element }\lstinline!x! & \textbf{\small{}Previous accumulator} & \textbf{\small{}Next accumulator}\tabularnewline
\hline 
\hline 
{\small{}}\lstinline!"a"! & {\small{}}\lstinline!(Seq(), Seq())! & {\small{}}\lstinline!(Seq(), Seq("a"))!\tabularnewline
\hline 
{\small{}}\lstinline!"b"! & {\small{}}\lstinline!(Seq(), Seq("a"))! & {\small{}}\lstinline!(Seq(("a","b")), Seq())!\tabularnewline
\hline 
{\small{}}\lstinline!"c"! & {\small{}}\lstinline!(Seq(("a","b")), Seq())! & {\small{}}\lstinline!(Seq(("a","b")), Seq("c"))!\tabularnewline
\hline 
\end{tabular}
\par\end{center}

Now it becomes clear how to implement the updater function:
\begin{lstlisting}
type Acc = (Seq[(A, A)], Seq[A])     // Type alias, for brevity.
def updater(acc: Acc, x: A): Acc = acc match {
    case (result, Seq())      => (result, Seq(x))
    case (result, Seq(prev))  => (result :+ ((prev, x)), Seq())
  }
\end{lstlisting}
We will call \lstinline!foldLeft! with this updater and then perform
some post-processing to make sure we create the last pair in case
the last iteration is odd-numbered, i.e., when the \textsf{``}holdover\textsf{''}
is not empty after \lstinline!foldLeft! is finished. In this implementation,
we use pattern matching to decide whether a sequence is empty:
\begin{lstlisting}
def toPairs[A](xs: Seq[A], default: A): Seq[(A, A)] = {
  type Acc = (Seq[(A, A)], Seq[A])     // Type alias, for brevity.
  def init: Acc = (Seq(), Seq())
  def updater(acc: Acc, x: A): Acc = acc match {
    case (result, Seq())      => (result, Seq(x))
    case (result, Seq(prev))  => (result :+ ((prev, x)), Seq())
  }
  val (result, holdover) = xs.foldLeft(init)(updater)
  holdover match {    // May need to append the last element to the result.
    case Seq()    => result
    case Seq(x)   => result :+ ((x, default))
  }
}
\end{lstlisting}
This code shows examples of partial functions that are applied safely.
One of these partial functions is used in the expression

\begin{wrapfigure}{l}{0.3\columnwidth}%
\vspace{-0.95\baselineskip}
\begin{lstlisting}
holdover match {
  case Seq()    => ...
  case Seq(a)   => ...
}
\end{lstlisting}

\vspace{-1.5\baselineskip}
\end{wrapfigure}%

\noindent This code works when \lstinline!holdover! is empty or has
length $1$ but fails for longer sequences. In the implementation
of \lstinline!toPairs!, the value of \lstinline!holdover! will always
be a sequence of length at most $1$, so it is safe to use this partial
function.

\subsection{Exercises: Using \texttt{foldLeft}}

\subsubsection{Exercise \label{subsec:Exercise-2.2-foldleft-1}\ref{subsec:Exercise-2.2-foldleft-1}}

Implement a function \lstinline!fromPairs! that performs the inverse
transformation to the \lstinline!toPairs! function defined in Example~\ref{subsec:Example-foldleft-7}.
The required type signature and a sample test are:
\begin{lstlisting}
def fromPairs[A](xs: Seq[(A, A)]): Seq[A] = ???

scala> fromPairs(Seq((1, 2), (3, 4)))
res0: Seq[Int] = List(1, 2, 3, 4)
\end{lstlisting}

Hint: This can be done with \lstinline!foldLeft! or with \lstinline!flatMap!.

\subsubsection{Exercise \label{subsec:Exercise-2.2-foldleft-2}\ref{subsec:Exercise-2.2-foldleft-2}}

Implement the \lstinline!flatten! method for sequences by using \lstinline!foldLeft!.
The required type signature and a sample test are:
\begin{lstlisting}
def flatten[A](xxs: Seq[Seq[A]]): Seq[A] = ???

scala> flatten(Seq(Seq(1, 2, 3), Seq(), Seq(4)))
res0: Seq[Int] = List(1, 2, 3, 4)
\end{lstlisting}


\subsubsection{Exercise \label{subsec:Exercise-2.2-foldleft-3}\ref{subsec:Exercise-2.2-foldleft-3}}

Use \lstinline!foldLeft! to implement the \lstinline!zipWithIndex!
method for sequences. The required type signature and a sample test:
\begin{lstlisting}
def zipWithIndex[A](xs: Seq[A]): Seq[(A, Int)] = ???

scala> zipWithIndex(Seq("a", "b", "c", "d"))
res0: Seq[String] = List((a, 0), (b, 1), (c, 2), (d, 3))
\end{lstlisting}


\subsubsection{Exercise \label{subsec:Exercise-2.2-foldleft-4}\ref{subsec:Exercise-2.2-foldleft-4}}

Use \lstinline!foldLeft! to implement a function \lstinline!filterMap!
that combines \lstinline!map! and \lstinline!filter! for sequences.
The required type signature and a sample test:
\begin{lstlisting}
def filterMap[A, B](xs: Seq[A])(pred: A => Boolean)(f: A => B): Seq[B] = ???

scala> filterMap(Seq(1, 2, 3, 4)) { x => x > 2 } { x => x * 10 }
res0: Seq[Int] = List(30, 40)
\end{lstlisting}


\subsubsection{Exercise \label{subsec:Exercise-2.2-foldleft-5}\ref{subsec:Exercise-2.2-foldleft-5}{*}}

Split a sequence into subsequences (\textsf{``}batches\textsf{''}) of length not larger
than a given maximum length $n$. The required type signature and
a sample test:
\begin{lstlisting}
def byLength[A](xs: Seq[A], length: Int): Seq[Seq[A]] = ???

scala> byLength(Seq("a", "b", "c", "d"), 2)
res0: Seq[Seq[String]] = List(List(a, b), List(c, d))

scala> byLength(Seq(1, 2, 3, 4, 5, 6, 7), 3)
res1: Seq[Seq[Int]] = List(List(1, 2, 3), List(4, 5, 6), List(7))
\end{lstlisting}


\subsubsection{Exercise \label{subsec:Exercise-2.2-foldleft-5-1}\ref{subsec:Exercise-2.2-foldleft-5-1}{*}}

Split a sequence into batches by \textsf{``}weight\textsf{''} computed via a given
function. The total weight of items in any batch should not be larger
than a given maximum weight. The required type signature and a sample
test:
\begin{lstlisting}
def byWeight[A](xs: Seq[A], maxW: Double)(w: A => Double): Seq[Seq[A]] = ???

scala> byWeight((1 to 10).toList, 5.75){ x => math.sqrt(x) }
res0: Seq[Seq[Int]] = List(List(1, 2, 3), List(4, 5), List(6, 7), List(8), List(9), List(10))
\end{lstlisting}


\subsubsection{Exercise \label{subsec:Exercise-2.2-foldleft-6}\ref{subsec:Exercise-2.2-foldleft-6}{*}}

Use \lstinline!foldLeft! to implement a \lstinline!groupBy! function.
The type signature and a test:
\begin{lstlisting}
def groupBy[A, K](xs: Seq[A])(by: A => K): Map[K, Seq[A]] = ???

scala> groupBy(Seq(1, 2, 3, 4, 5)){ x => x % 2 }
res0: Map[Int, Seq[Int]] = Map(1 -> List(1, 3, 5), 0 -> List(2, 4))
\end{lstlisting}

Hints: The accumulator should be of type \lstinline!Map[K, Seq[A]]!.
To work with dictionaries, you will need to use the methods \lstinline!getOrElse!
and \lstinline!updated!. The method \lstinline!getOrElse! fetches
a value from a dictionary by key, and returns the given default value
if the dictionary does not contain that key:
\begin{lstlisting}
scala> Map("a" -> 1, "b" -> 2).getOrElse("a", 300)
res0: Int = 1

scala> Map("a" -> 1, "b" -> 2).getOrElse("c", 300)
res1: Int = 300
\end{lstlisting}
The method \lstinline!updated! produces a new dictionary that contains
a new value for the given key, whether or not that key already exists
in the dictionary:
\begin{lstlisting}
scala> Map("a" -> 1, "b" -> 2).updated("c", 300) // Key is new.
res0: Map[String,Int] = Map(a -> 1, b -> 2, c -> 300)

scala> Map("a" -> 1, "b" -> 2).updated("a", 400) // Key already exists.
res1: Map[String,Int] = Map(a -> 400, b -> 2) 
\end{lstlisting}


\section{Converting a single value into a sequence\label{sec:ch2Converting-a-single}}

An aggregation converts (\textsf{``}folds\textsf{''}) a sequence into a single value;
the opposite operation (\textsf{``}unfolding\textsf{''}) converts a single value into
a sequence. An example of this task is to compute the sequence of
decimal digits for a given integer:

\begin{wrapfigure}{l}{0.37\columnwidth}%
\vspace{-1\baselineskip}
\begin{lstlisting}
def digitsOf(x: Int): Seq[Int] = ???

scala> digitsOf(2405)
res0: Seq[Int] = List(2, 4, 0, 5)
\end{lstlisting}

\vspace{-1.5\baselineskip}
\end{wrapfigure}%

\noindent We cannot implement \lstinline!digitsOf! using \lstinline!map!,
\lstinline!zip!, or \lstinline!foldLeft!, because these methods
work only if we \emph{already have} a sequence; but the function \lstinline!digitsOf!
needs to create a new sequence. We could create a sequence via the
expression \lstinline!(1 to n)! if the required length of the sequence
were known in advance. However, the function \lstinline!digitsOf!
must produce a sequence whose length is determined by a condition
that we cannot easily evaluate in advance.

A general \textsf{``}unfolding\textsf{''} operation needs to build a sequence whose
length is not determined in advance. This kind of sequence is called
a \index{stream}\textbf{stream}. The elements of a stream are computed
only when necessary (unlike the elements of \lstinline!List! or \lstinline!Array!,
which are all computed in advance). The unfolding operation will compute
next elements on demand; this creates a stream. We can then apply
\lstinline!takeWhile! to the stream, in order to stop it when a certain
condition holds. Finally, if required, the truncated stream may be
converted to a list or another type of sequence. In this way, we can
generate a sequence of initially unknown length according to any given
requirements.

The Scala library has a general stream-producing function \lstinline!Stream.iterate!.\footnote{In a future version of Scala, the \lstinline!Stream! class will be
replaced by \lstinline!LazyList!.} This function has two arguments, the initial value and a function
that computes the next value from the previous one:

\begin{wrapfigure}{l}{0.5\columnwidth}%
\vspace{-0.7\baselineskip}
\begin{lstlisting}
scala> Stream.iterate(2) { x => x + 10 }
res0: Stream[Int] = Stream(2, ?)
\end{lstlisting}

\vspace{-1\baselineskip}
\end{wrapfigure}%

\noindent The stream is ready to start computing the next elements
of the sequence (so far, only the first element, \lstinline!2!, has
been computed). In order to see the next elements, we need to stop
the stream at a finite size and then convert the result to a list:
\begin{lstlisting}
scala> Stream.iterate(2) { x => x + 10 }.take(6).toList
res1: List[Int] = List(2, 12, 22, 32, 42, 52)
\end{lstlisting}
If we try to evaluate \lstinline!toList! on a stream without first
limiting its size via \lstinline!take! or \lstinline!takeWhile!,
the program will keep producing more elements of the stream until
it runs out of memory and crashes.

Streams are similar to sequences, and methods such as \lstinline!map!,
\lstinline!filter!, and \lstinline!flatMap! are also defined for
streams. For instance, the method \lstinline!drop! skips a given
number of initial elements:
\begin{lstlisting}
scala> Seq(10, 20, 30, 40, 50).drop(3)
res2: Seq[Int] = List(40, 50)

scala> Stream.iterate(2) { x => x + 10 }.drop(3)
res3: Stream[Int] = Stream(32, ?)
\end{lstlisting}
This example shows that in order to evaluate \lstinline!drop(3)!,
the stream had to compute its elements up to \lstinline!32! (but
the subsequent elements are still not computed).

To figure out the code for \lstinline!digitsOf!, we first write this
function as a mathematical formula. To compute the digits for, say,
$n=2405$, we need to divide $n$ repeatedly by $10$, getting a sequence
$n_{k}$ of intermediate numbers ($n_{0}=2405$, $n_{1}=240$, ...)
and the corresponding sequence of last digits, $n_{k}\text{ mod }10$
(in this example: $5$, $0$, ...). The sequence $n_{k}$ is defined
using mathematical induction:
\begin{quotation}
$\bullet$ Base case: $n_{0}=n$, where $n$ is a given initial integer.

$\bullet$ Inductive step: $n_{k+1}=\left\lfloor \frac{n_{k}}{10}\right\rfloor \ \text{for}\ k=1,2,...$
\end{quotation}
Here $\left\lfloor \frac{n_{k}}{10}\right\rfloor $ is the mathematical
notation for the integer division by $10$. Let us tabulate the evaluation
of the sequence $n_{k}$ for $n=2405$: 

\begin{wraptable}{l}{0.47\columnwidth}%
\begin{centering}
\vspace{-0.85\baselineskip}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline 
{\small{}$k=$} & {\small{}$0$} & {\small{}$1$} & {\small{}$2$} & {\small{}$3$} & {\small{}$4$} & {\small{}$5$} & {\small{}$6$}\tabularnewline
\hline 
{\small{}$n_{k}=$} & {\small{}$2405$} & {\small{}$240$} & {\small{}$24$} & {\small{}$2$} & {\small{}$0$} & {\small{}$0$} & {\small{}$0$}\tabularnewline
\hline 
{\small{}$n_{k}\text{ mod }10=$} & {\small{}$5$} & {\small{}$0$} & {\small{}$4$} & {\small{}$2$} & {\small{}$0$} & {\small{}$0$} & {\small{}$0$}\tabularnewline
\hline 
\end{tabular}
\par\end{centering}
\vspace{-1\baselineskip}
\end{wraptable}%

\noindent The numbers $n_{k}$ will remain all zeros after $k=4$.
It is clear that the useful part of the sequence is before it becomes
all zeros. In this example, the sequence $n_{k}$ needs to be stopped
at $k=4$. The sequence of digits then becomes $\left[5,0,4,2\right]$,
and we need to reverse it to obtain $\left[2,4,0,5\right]$. For reversing
a sequence, the Scala library has the standard method \lstinline!reverse!.
So, a complete implementation for \lstinline!digitsOf! is:
\begin{lstlisting}
def digitsOf(n: Int): Seq[Int] =
  if (n == 0) Seq(0) else { // n == 0 is a special case.
    Stream.iterate(n) { nk => nk / 10 }
      .takeWhile { nk => nk != 0 }
      .map { nk => nk % 10 }
      .toList.reverse
  }
\end{lstlisting}
We can shorten the code by using the syntax such as \lstinline!(_ % 10)!
instead of \lstinline!{ nk => nk % 10 }!, 
\begin{lstlisting}
def digitsOf(n: Int): Seq[Int] =
  if (n == 0) Seq(0) else { // n == 0 is a special case.
    Stream.iterate(n)(_ / 10)
      .takeWhile(_ != 0)
      .map(_ % 10)
      .toList.reverse
  }
\end{lstlisting}

The type signature of the method \lstinline!Stream.iterate! can be
written as
\begin{lstlisting}
def iterate[A](init: A)(next: A => A): Stream[A]
\end{lstlisting}
and shows a close correspondence to a definition by mathematical induction.
The base case is the first value, \lstinline!init!, and the inductive
step is a function, \lstinline!next!, that computes the next element
from the previous one. It is a general way of creating sequences whose
length is not determined in advance.

\section{Transforming a sequence into another sequence}

We have seen methods such as \lstinline!map! and \lstinline!zip!
that transform sequences into sequences. However, these methods cannot
express a general transformation where the elements of the new sequence
are defined by induction and depend on previous elements. An example
of this kind is computing the partial sums of a given sequence $x_{i}$,
say $b_{k}=\sum_{i=0}^{k-1}x_{i}$. This formula defines $b_{0}=0$,
$b_{1}=x_{0}$, $b_{2}=x_{0}+x_{1}$, $b_{3}=x_{0}+x_{1}+x_{2}$,
etc. A definition via mathematical induction may be written like this:
\begin{quotation}
$\bullet$ Base case: $b_{0}=0$.

$\bullet$ Inductive step: Given $b_{k}$, we define $b_{k+1}=b_{k}+x_{k}$
for $k=0,1,2,...$
\end{quotation}
The Scala library method \lstinline!scanLeft! implements a general
sequence-to-sequence transformation defined in this way. The code
implementing the partial sums is
\begin{lstlisting}
def partialSums(xs: Seq[Int]): Seq[Int] = xs.scanLeft(0){ (x, y) => x + y }

scala> partialSums(Seq(1, 2, 3, 4))
res0: Seq[Int] = List(0, 1, 3, 6, 10)
\end{lstlisting}
The first argument of \lstinline!scanLeft! is the base case, and
the second argument is an updater function describing the inductive
step. In general, the type of elements of the second sequence is different
from that of the first sequence. The updater function takes an element
of the first sequence and a previous element of the second sequence,
and returns the next element of the second sequence. Note that the
result of \lstinline!scanLeft! is one element longer than the original
sequence, because the base case provides an initial value.

Until now, we have seen that \lstinline!foldLeft! is sufficient to
re-implement almost every method that work on sequences, such as \lstinline!map!,
\lstinline!filter!, or \lstinline!flatten!. Let us show, as an illustration,
how to implement the method \lstinline!scanLeft! via \lstinline!foldLeft!.
In the implementation, the accumulator contains the previous element
of the second sequence together with a growing fragment of that sequence,
which is updated as we iterate over the first sequence. The code is

\begin{wrapfigure}{l}{0.565\columnwidth}%
\vspace{-0.95\baselineskip}
\begin{lstlisting}[numbers=left]
def scanLeft[A, B](xs: Seq[A])(b0: B)(next: (B, A) => B)
    : Seq[B] = {
  val init: (B, Seq[B]) = (b0, Seq(b0))
  val (_, result) = xs.foldLeft(init) {
    case ((b, seq), x) =>
      val newB = next(b, x)
      (newB, seq :+ newB)
  }
  result
}
\end{lstlisting}

\vspace{-1.2\baselineskip}
\end{wrapfigure}%

\noindent To implement the (nameless) updater function for \lstinline!foldLeft!
in lines 5\textendash 8, we used the Scala feature that makes it easier
to define functions with several arguments containing tuples. In our
case, the updater function in \lstinline!foldLeft! has two arguments:
the first is a tuple \lstinline!(B, Seq[B])!, the second is a value
of type \lstinline!A!. The pattern expression \lstinline!case ((b, seq), x) =>!
appears to match a nested tuple\index{tuples!nested in pattern matching}.
In reality, this expression matches the two arguments of the updater
function and, at the same time, destructures the tuple argument as
\lstinline!(b, seq)!. 

\section{Summary}

We have seen a broad overview of translating mathematical induction
into Scala code.

What problems can we solve now?
\begin{itemize}
\item Compute mathematical expressions involving arbitrary recursion.
\item Use the accumulator trick to enforce tail recursion.
\item Implement functions with type parameters.
\item Use arbitrary inductive (i.e., recursive) formulas to:
\begin{itemize}
\item convert sequences to single values (aggregation or \textsf{``}folding\textsf{''});
\item create new sequences from single values (\textsf{``}unfolding\textsf{''});
\item transform existing sequences into new sequences.
\end{itemize}
\end{itemize}
\begin{wraptable}{l}{0.59\columnwidth}%
\begin{centering}
\vspace{-0.5\baselineskip}
\begin{tabular}{|c|c|}
\hline 
\textbf{\small{}Definition by induction} & \textbf{\small{}Scala code example}\tabularnewline
\hline 
\hline 
{\small{}$f(\left[\right])=b~;~~f(s\pplus[x])=g(f(s),x)$} & {\small{}}\lstinline!f(xs) = xs.foldLeft(b)(g)!\tabularnewline
\hline 
{\small{}$x_{0}=b~;~~x_{k+1}=g(x_{k})$} & {\small{}}\lstinline!xs = Stream.iterate(b)(g)!\tabularnewline
\hline 
{\small{}$y_{0}=b~;~~y_{k+1}=g(y_{k},x_{k})$} & {\small{}}\lstinline!ys = xs.scanLeft(b)(g)!\tabularnewline
\hline 
\end{tabular}
\par\end{centering}
\caption{Implementing mathematical induction.\label{tab:Implementing-mathematical-induction}}
\vspace{-0.75\baselineskip}
\end{wraptable}%

\noindent Table~\ref{tab:Implementing-mathematical-induction} shows
Scala code implementing those tasks. Iterative calculations are implemented
by translating mathematical induction directly into code. In the functional
programming paradigm, the programmer does not need to write loops
or use array indices. Instead, the programmer reasons about sequences
as mathematical values: \textsf{``}Starting from this value, we get that sequence,
then transform it into that other sequence,\textsf{''} etc. This is a powerful
way of working with sequences, dictionaries, and sets. Many kinds
of programming errors (such as using an incorrect array index) are
avoided from the outset, and the code is shorter and easier to read
than code written via loops.

\paragraph*{What tasks are not possible with these tools?}

We cannot implement a non-tail-recursive function without stack overflow
(i.e., without unlimited growth of intermediate expressions). The
accumulator trick does not always work! In some cases, it is impossible
to implement tail recursion in a given recursive computation. An example
of such a computation is the \textsf{``}merge-sort\textsf{''} algorithm where the
function body must contain two recursive calls within a single expression.
(It is impossible to rewrite \emph{two} recursive calls as one.) 

What if our recursive code cannot be transformed into tail-recursive
code via the accumulator trick, but the recursion depth is so large
that stack overflows occur? There exist special tricks (e.g., \textsf{``}continuations\textsf{''}\index{continuation-passing}
and \textsf{``}trampolines\textsf{''}\index{trampolines}) that convert non-tail-recursive
code into iterative code without stack overflows. Those techniques
are beyond the scope of this book.

\subsection{Solved examples\index{solved examples}}

\subsubsection{Example \label{subsec:ch2Example-seq-1}\ref{subsec:ch2Example-seq-1}}

Compute the smallest $n$ such that $f(f(f(...f(1)...)\geq1000$,
where the function $f$ is applied $n$ times. Write this as a function
taking $f$, $1$, and $1000$ as arguments. Test with $f(x)=2x+1$.

\subparagraph{Solution}

Define a stream of values $\left[1,f(1),f(f(1)),...\right]$ and use
\lstinline!takeWhile! to stop the stream when the values reach $1000$.
The number $n$ is then found as the length of the resulting sequence
plus $1$: 
\begin{lstlisting}
scala> Stream.iterate(1)(x => 2 * x + 1).takeWhile(x => x < 1000).toList
res0: List[Int] = List(1, 3, 7, 15, 31, 63, 127, 255, 511)

scala> 1 + Stream.iterate(1)(x => 2 * x + 1).takeWhile(x => x < 1000).length
res1: Int = 10
\end{lstlisting}


\subsubsection{Example \label{subsec:ch2Example-seq-2}\ref{subsec:ch2Example-seq-2}}

\textbf{(a)} For a given \lstinline!Stream[Int]!, compute the stream
of the largest values seen so far.

\textbf{(b)} Compute the stream of $k$ largest values seen so far
($k$ is a given integer parameter).

\subparagraph{Solution:}

We cannot use \lstinline!max! or sort the entire stream, since the
length of the stream is not known in advance. So we need to use \lstinline!scanLeft!,
which will build the output stream one element at a time.

\textbf{(a)} Maintain the largest value seen so far in the accumulator
of the \lstinline!scanLeft!:
\begin{lstlisting}
def maxSoFar(xs: Stream[Int]): Stream[Int] =
  xs.scanLeft(xs.head) { (max, x) => math.max(max, x) }.drop(1)
\end{lstlisting}
We use \lstinline!.drop(1)! to remove the initial value, \lstinline!xs.head!,
because it is not useful for our result but is always produced by
\lstinline!scanLeft!.

To test this function, let us define a stream whose values go up and
down:
\begin{lstlisting}
val s = Stream.iterate(0)(x => 1 - 2 * x)

scala> s.take(10).toList
res0: List[Int] = List(0, 1, -1, 3, -5, 11, -21, 43, -85, 171)

scala> maxSoFar(s).take(10).toList
res1: List[Int] = List(0, 1, 1, 3, 3, 11, 11, 43, 43, 171)
\end{lstlisting}

\textbf{(b)} We again use \lstinline!scanLeft!, where now the accumulator
needs to keep the largest $k$ values seen so far. There are two ways
of maintaining this accumulator: First, to have a sequence of $k$
values that we sort and truncate each time. Second, to use a specialized
data structure such as a priority queue that automatically keeps values
sorted and its length bounded. For the purposes of this example, let
us avoid using specialized data structures:
\begin{lstlisting}
def maxKSoFar(xs: Stream[Int], k: Int): Stream[Seq[Int]] = {
  // The initial value of the accumulator is an empty Seq() of type Seq[Int].
  xs.scanLeft(Seq[Int]()) { (seq, x) =>
  // Sort in descending order, and take the first k values.
    (seq :+ x).sorted.reverse.take(k)
  }.drop(1) // Skip the undesired first value.
}

scala> maxKSoFar(s, 3).take(10).toList
res2: List[Seq[Int]] = List(List(0), List(1, 0), List(1, 0, -1), List(3, 1, 0), List(3, 1, 0), List(11, 3, 1), List(11, 3, 1), List(43, 11, 3), List(43, 11, 3), List(171, 43, 11)) 
\end{lstlisting}


\subsubsection{Example \label{subsec:ch2Example-seq-3}\ref{subsec:ch2Example-seq-3}}

Find the last element of a non-empty sequence. (Hint: use \lstinline!reduce!.)

\subparagraph{Solution}

This function is available in the Scala library as the standard method
\lstinline!last! on sequences. Here we need to re-implement it using
\lstinline!reduce!. Begin by writing an inductive definition:
\begin{quotation}
$\bullet$ (Base case.) \lstinline!last(Seq(x)) == x!.

$\bullet$ (Inductive step.) \lstinline!last(x +: xs) == last(xs)!
assuming \lstinline!xs! is non-empty.
\end{quotation}
The \lstinline!reduce! method implements an inductive aggregation
similarly to \lstinline!foldLeft!, except that for \lstinline!reduce!
the base case  always returns \lstinline!x! for a $1$-element sequence
\lstinline!Seq(x)!. This is exactly what we need here, so the inductive
definition is directly translated into code, with the updater function
$g(x,y)=y$:
\begin{lstlisting}
def last[A](xs: Seq[A]): A = xs.reduce { (x, y) => y }
\end{lstlisting}


\subsubsection{Example \label{subsec:ch2Example-seq-9}\ref{subsec:ch2Example-seq-9}}

\textbf{(a)} Count the occurrences of each distinct word in a string:
\begin{lstlisting}
def countWords(s: String): Map[String, Int] = ???

scala> countWords("a quick a quick a brown a fox")
res0: Map[String, Int] = Map(a -> 4, quick -> 2, brown -> 1, fox -> 1)
\end{lstlisting}
\textbf{(b)} Count the occurrences of each distinct element in a sequence
of type \lstinline!Seq[A]!.

\subparagraph{Solution}

\textbf{(a)} We split the string into an array of words via \lstinline!s.split(" ")!,
and apply a \lstinline!foldLeft! to that array, since the computation
is a kind of aggregation over the array of words. The accumulator
of the aggregation will be the dictionary of word counts for all the
words seen so far:
\begin{lstlisting}
def countWords(s: String): Map[String, Int] = {
  val init: Map[String, Int] = Map()
  s.split(" ").foldLeft(init) { (dict, word) =>
    val newCount = dict.getOrElse(word, 0) + 1
    dict.updated(word, newCount)
  }
}
\end{lstlisting}
An alternative, shorter implementation of the same function is
\begin{lstlisting}
def countWords(s: String): Map[String, Int] = s.split(" ").groupBy(w => w).mapValues(_.length)
\end{lstlisting}
The \lstinline!groupBy! creates a dictionary in one function call
rather than one entry at a time. But the resulting dictionary contains
word lists instead of word counts, so we use \lstinline!mapValues!:
\begin{lstlisting}
scala> "a a b b b c".split(" ").groupBy(w => w)
res0: Map[String,Array[String]] = Map(b -> Array(b, b, b), a -> Array(a, a), c -> Array(c))

scala> res0.mapValues(_.length)
res1: Map[String,Int] = Map(b -> 3, a -> 2, c -> 1)
\end{lstlisting}

\textbf{(b)} The main code of \lstinline!countWords! does not depend
on the fact that words are of type \lstinline!String!. It will work
in the same way for any other type of keys for the dictionary. So
we keep the same code (except for renaming \lstinline!word! to \lstinline!x!)
and replace \lstinline!String! by a type parameter \lstinline!A!
in the type signature:
\begin{lstlisting}
def countValues[A](xs: Seq[A]): Map[A, Int] =
  xs.foldLeft(Map[A, Int]()) { (dict, x) =>
    val newCount = dict.getOrElse(x, 0) + 1
    dict.updated(x, newCount)
  }

scala> countValues(Seq(100, 100, 200, 100, 200, 200, 100))
res0: Map[Int,Int] = Map(100 -> 4, 200 -> 3)
\end{lstlisting}


\subsubsection{Example \label{subsec:ch2Example-binary-search-seq-4}\ref{subsec:ch2Example-binary-search-seq-4}}

\textbf{(a)} Implement the binary search\index{binary search} algorithm\footnote{\texttt{\href{https://en.wikipedia.org/wiki/Binary_search_algorithm}{https://en.wikipedia.org/wiki/Binary\_search\_algorithm}}}
for a sorted sequence \lstinline!xs: Seq[Int]! as a function returning
the index of the requested value \lstinline!goal! (assume that \lstinline!xs!
always contains \lstinline!goal!):
\begin{lstlisting}
@tailrec def binSearch(xs: Seq[Int], goal: Int): Int = ???

scala> binSearch(Seq(1, 3, 5, 7), 5)
res0: Int = 2
\end{lstlisting}

\textbf{(b)} Re-implement \lstinline!binSearch! using \lstinline!Stream.iterate!
without writing explicitly recursive code.

\subparagraph{Solution}

\textbf{(a)} The binary search algorithm splits the array into two
halves and may continue the search recursively in one of the halves.
We need to write the solution as a tail-recursive function with an
additional accumulator argument. So we expect that the code should
look like this:
\begin{lstlisting}
@tailrec def binSearch(xs: Seq[Int], goal: Int, acc: _ = ???): Int = {
  if (???) acc  // This condition must decide whether we are finished.
  else {
    // Determine which half of the sequence contains `goal`.
    // Then update the accumulator accordingly.
    val newAcc = ???
    binSearch(xs, goal, newAcc) // Tail-recursive call.
  }
}
\end{lstlisting}
We will first decide the type and the initial value of the accumulator,
then implement the updater.

The information required for the recursive call must show the segment
of the sequence where the target number is present. That segment is
defined by two indices $i$, $j$ representing the left and the right
bounds of the sub-sequence, such that the target element is $x_{n}$
with $x_{i}\leq x_{n}\leq x_{j-1}$. It follows that the accumulator
should be a pair of two integers $\left(i,j\right)$. The initial
value of the accumulator is the pair $\left(0,N\right)$, where $N$
is the length of the entire sequence. The search is finished when
$i+1=j$. For convenience, let us introduce \emph{two} accumulator
values representing $\left(i,j\right)$:
\begin{lstlisting}
@tailrec def binSearch(xs: Seq[Int], goal: Int)(left: Int = 0, right: Int = xs.length): Int = {
  // Check whether `goal` is at one of the boundaries.
  if (right - left <= 1 || xs(left) == goal) left
  else {
    val middle = (left + right) / 2
    // Determine which half of the array contains `target`.
    // Update the accumulator accordingly.
    val (newLeft, newRight) =
      if (goal < xs(middle)) (left, middle)
      else (middle, right)
    binSearch(xs, goal)(newLeft, newRight) // Tail-recursive call.
  }
}

scala> binSearch(0 to 10, 3)() // Default accumulator values.
res0: Int = 3
\end{lstlisting}
Here we used a feature of Scala that allows us to set \lstinline!xs.length!
as a default value for the argument \lstinline!right! of \lstinline!binSearch!.
This works because \lstinline!right! is in a different \textbf{argument
list}\index{argument list} from \lstinline!xs!. Default values in
an argument list may depend on arguments in a \emph{previous} argument
list. However, the code
\begin{lstlisting}
def binSearch(xs: Seq[Int], goal: Int, left: Int = 0, right: Int = xs.length)
\end{lstlisting}
will generate an error: the arguments in the same argument list cannot
depend on each other. (The error will say \lstinline!not found: value xs!.)

\textbf{(b)} We can visualize the binary search as a procedure that
generates a stream of progressively tighter bounds for the location
of \lstinline!goal!. The initial bounds are \lstinline!(0, xs.length)!,
and the final bounds are \lstinline!(k, k+1)! for some \lstinline!k!.
We can generate the sequence of bounds using \lstinline!Stream.iterate!
and stop the sequence when the bounds become sufficiently tight. To
detect that, we use the \lstinline!find! method. The code becomes:
\begin{lstlisting}
def binSearch(xs: Seq[Int], goal: Int): Int = {
  type Acc = (Int, Int)
  val init: Acc = (0, xs.length)
  val updater: Acc => Acc = { case (left, right) =>
    if (right - left <= 1 || xs(left) == goal) (left, left + 1)
    else {
      val middle = (left + right) / 2
      // Determine which half of the array contains `target`.
      // Update the accumulator accordingly.
      if (goal < xs(middle)) (left, middle)
      else (middle, right)
    }
  }
  Stream.iterate(init)(updater)
    .find { case (x, y) => y - x <= 1 }  // Find the element with tight enough bounds.
    .get._1                              // Take the `left` bound from that element.
}
\end{lstlisting}
In this code, recursion is delegated to \lstinline!Stream.iterate!
and is cleanly separated from the \textsf{``}business logic\textsf{''} (i.e., implementing
the base case, the inductive step, and the post-processing).

\subsubsection{Example \label{subsec:ch2sumdigitsExample-seq-5}\ref{subsec:ch2sumdigitsExample-seq-5}}

For a given positive \lstinline!n:Int!, compute the sequence $\left[s_{0},s_{1},s_{2},...\right]$
defined by $s_{0}=SD(n)$ and $s_{k}=SD(s_{k-1})$ for $k>0$, where
$SD(x)$ is the sum of the decimal digits of the integer $x$, e.g.,
$SD(123)=6$. Stop the sequence $s_{i}$ when the numbers begin repeating.
For example, $SD(99)=18$, $SD(18)=9$, $SD(9)=9$. So, for $n=99$,
the sequence $s_{i}$ must be computed as $\left[99,18,9\right]$.

Hint: use \lstinline!Stream.iterate! and \lstinline!scanLeft!.

\subparagraph{Solution}

We need to implement a function \lstinline!sdSeq! having the type
signature
\begin{lstlisting}
def sdSeq(n: Int): Seq[Int]
\end{lstlisting}
First, we need to implement $SD(x)$. The sum of digits is obtained
similarly to Section~\ref{sec:ch2Converting-a-single}:
\begin{lstlisting}
def SD(n: Int): Int = if (n == 0) 0 else Stream.iterate(n)(_ / 10).takeWhile(_ != 0).map(_ % 10).sum
\end{lstlisting}
Let us compute the sequence $\left[s_{0},s_{1},s_{2},...\right]$
by repeatedly applying \lstinline!SD! to some number, say, \lstinline!99!:
\begin{lstlisting}
scala> Stream.iterate(99)(SD).take(10).toList
res1: List[Int] =  List(99, 18, 9, 9, 9, 9, 9, 9, 9, 9)
\end{lstlisting}
We need to stop the stream when the values start to repeat, keeping
the first repeated value. In the example above, we need to stop the
stream after the value \lstinline!9! (but include that value). One
solution is to transform the stream via \lstinline!scanLeft! into
a stream of \emph{pairs} of consecutive values, so that detecting
repetition becomes quick:
\begin{lstlisting}
scala> Stream.iterate(99)(SD).scanLeft((0,0)) { case ((prev, x), next) => (x, next) }.take(8).toList
res2: List[(Int, Int)] = List((0,0), (0,99), (99,18), (18,9), (9,9), (9,9), (9,9), (9,9))

scala> res2.drop(1).takeWhile { case (x, y) => x  != y }
res3: List[(Int, Int)] = List((0,99), (99,18), (18,9))
\end{lstlisting}
This looks right; it remains to remove the first parts of the tuples:
\begin{lstlisting}
def sdSeq(n: Int): Seq[Int] = Stream.iterate(n)(SD)            // Stream[Int]
    .scanLeft((0,0)) { case ((prev, x), next) => (x, next) }   // Stream[(Int, Int)]
    .drop(1).takeWhile { case (x, y) => x  != y }              // Stream[(Int, Int)]
    .map(_._2)                                                 // Stream[Int]
    .toList                                                    // List[Int]

scala> sdSeq(99)
res3: Seq[Int] = List(99, 18, 9)
\end{lstlisting}


\subsubsection{Example \label{subsec:ch2Example-stream}\ref{subsec:ch2Example-stream}}

Implement a \index{unfold function@\texttt{unfold} function}function
\lstinline!unfold! with the type signature
\begin{lstlisting}
def unfold[A](init: A)(next: A => Option[A]): Stream[A]
\end{lstlisting}
The function should create a stream of values of type \lstinline!A!
with the initial value \lstinline!init!. Next elements are computed
from previous ones via the function \lstinline!next! until it returns
\lstinline!None!. An example test:
\begin{lstlisting}
scala> unfold(0) { x => if (x > 5) None else Some(x + 2) }
res0: Stream[Int] = Stream(0, ?)

scala> res0.toList
res1: List[Int] = List(0, 2, 4, 6)
\end{lstlisting}


\subparagraph{Solution}

We can formulate the task as an inductive definition of a stream.
If \lstinline!next(init) == None!, the stream must stop at \lstinline!init!.
(This is the base case of the induction). Otherwise, \lstinline!next(init) == Some(x)!
yields a new value \lstinline!x! and indicates that we need to continue
to \textsf{``}unfold\textsf{''} the stream with \lstinline!x! instead of \lstinline!init!.
(This is the inductive step.) Streams can be created from individual
values via the Scala standard library method \lstinline!Stream.cons!
that constructs a stream from a single value and a tail:
\begin{lstlisting}
def unfold[A](init: A)(next: A => Option[A]): Stream[A] = next(init) match {
  case None      => Stream(init)                   // A stream containing a single value `init`.
  case Some(x)   => Stream.cons(init, unfold(x)(next)) // `init` followed by the tail of stream.
}
\end{lstlisting}


\subsubsection{Example \label{subsec:ch2Example-seq-6}\ref{subsec:ch2Example-seq-6}}

For a given stream $\left[s_{0},s_{1},s_{2},...\right]$ of type \lstinline!Stream[T]!,
compute the \textsf{``}half-speed\textsf{''} stream $h=\left[s_{0},s_{0},s_{1},s_{1},s_{2},s_{2},...\right]$.
The half-speed sequence $h$ is defined as $h_{2k}=h_{2k+1}=s_{k}$
for $k=0,1,2,...$

\subparagraph{Solution}

We use \lstinline!map! to replace each element $s_{i}$ by a sequence
containing two copies of $s_{i}$. Let us try this on a sample sequence:
\begin{lstlisting}
scala> Seq(1,2,3).map( x => Seq(x, x))
res0: Seq[Seq[Int]] = List(List(1, 1), List(2, 2), List(3, 3))
\end{lstlisting}
The result is almost what we need, except we need to \lstinline!flatten!
the nested list:
\begin{lstlisting}
scala> Seq(1,2,3).map( x => Seq(x, x)).flatten
res1: Seq[Seq[Int]] = List(1, 1, 2, 2, 3, 3)
\end{lstlisting}
The composition of \lstinline!map! and \lstinline!flatten! is \lstinline!flatMap!,
so the final code is
\begin{lstlisting}
def halfSpeed[T](str: Stream[T]): Stream[T] = str.flatMap(x => Seq(x, x))

scala> halfSpeed(Seq(1,2,3).toStream)
res2: Stream[Int] = Stream(1, ?)

scala> halfSpeed(Seq(1,2,3).toStream).toList
res3: List[Int] = List(1, 1, 2, 2, 3, 3)
\end{lstlisting}


\subsubsection{Example \label{subsec:ch2Example-seq-7}\ref{subsec:ch2Example-seq-7}}

(\index{loop detection}The \textbf{loop detection} problem.) Stop
a given stream $\left[s_{0},s_{1},s_{2},...\right]$ at a place $k$
where the sequence repeats itself; that is, an element $s_{k}$ equals
some earlier element $s_{i}$ with $i<k$.

\subparagraph{Solution}

The trick is to create a half-speed sequence $h_{i}$ out of $s_{i}$
and then find an index $k>0$ such that $h_{k}=s_{k}$. (The condition
$k>0$ is needed because we will always have $h_{0}=s_{0}$.) If we
find such an index $k$, it would mean that either $s_{k}=s_{k/2}$
or $s_{k}=s_{\left(k-1\right)/2}$; in either case, we will have found
an element $s_{k}$ that equals an earlier element. 

As an example, for an input sequence $s=\left[1,3,5,7,9,3,5,7,9,...\right]$
we obtain the half-speed sequence $h=\left[1,1,3,3,5,5,7,7,9,9,3,3,...\right]$.
Looking for an index $k>0$ such that $h_{k}=s_{k}$, we find that
$s_{7}=h_{7}=7$. The element $s_{7}$ indeed repeats an earlier element
(although $s_{7}$ is not the first such repetition).

There are in principle two ways of finding an index $k>0$ such that
$h_{k}=s_{k}$: First, to iterate over a list of indices $k=1,2,...$
and evaluate the condition $h_{k}=s_{k}$ as a function of $k$. Second,
to build a sequence of pairs $\left(h_{i},s_{i}\right)$ and use \lstinline!takeWhile!
to stop at the required index. In the present case, we cannot use
the first way because we do not have a fixed set of indices to iterate
over. Also, the condition $h_{k}=s_{k}$ cannot be directly evaluated
as a function of $k$ because $s$ and $h$ are streams that compute
elements on demand, not lists whose elements are computed in advance
and ready for use. 

So the code must iterate over a stream of pairs $\left(h_{i},s_{i}\right)$:
\begin{lstlisting}
def stopRepeats[T](str: Stream[T]): Stream[T] = {
  val halfSpeed = str.flatMap(x => Seq(x, x))
  val result = halfSpeed.zip(str) // Stream[(T, T)]
  .drop(1) // Enforce the condition k > 0.
  .takeWhile { case (h, s) => h != s } // Stream[(T, T)]
  .map(_._2) // Stream[T]
  str.head +: result // Prepend the first element that was dropped.
}

scala> stopRepeats(Seq(1, 3, 5, 7, 9, 3, 5, 7, 9).toStream).toList
res0: List[Int] = List(1, 3, 5, 7, 9, 3, 5)
\end{lstlisting}


\subsubsection{Example \label{subsec:ch2Example-seq-8}\ref{subsec:ch2Example-seq-8}}

Reverse each word in a string, but keep the order of words:
\begin{lstlisting}
def revWords(s: String): String = ???

scala> revWords("A quick brown fox")
res0: String = A kciuq nworb xof
\end{lstlisting}


\subparagraph{Solution}

The standard method \lstinline!split! converts a string into an array
of words:
\begin{lstlisting}
scala> "pa re ci vo mu".split(" ")
res0: Array[String] = Array(pa, re, ci, vo, mu)
\end{lstlisting}
Each word is reversed with \lstinline!reverse!; the resulting array
is concatenated into a string with \lstinline!mkString!:
\begin{lstlisting}
def revWords(s: String): String = s.split(" ").map(_.reverse).mkString(" ")
\end{lstlisting}


\subsubsection{Example \label{subsec:ch2Example-seq-10}\ref{subsec:ch2Example-seq-10}}

Remove adjacent repeated characters from a string:
\begin{lstlisting}
def noDups(s: String): String = ???

scala> noDups("abbcdeeeeefddgggggh")
res0: String = abcdefdgh
\end{lstlisting}


\subparagraph{Solution}

A string is automatically converted into a sequence of characters
when we use methods such as \lstinline!map! or \lstinline!zip! on
it. So, we can use \lstinline!s.zip(s.tail)! to get a sequence of
pairs $\left(s_{k},s_{k+1}\right)$ where $c_{k}$ is the $k$-th
character of the string $s$. A \lstinline!filter! will then remove
elements $s_{k}$ for which $s_{k+1}=s_{k}$:
\begin{lstlisting}
scala> val s = "abbcd"
s: String = abbcd

scala> s.zip(s.tail).filter { case (sk, skPlus1) => sk != skPlus1 }
res0: IndexedSeq[(Char, Char)] = Vector((a,b), (b,c), (c,d))
\end{lstlisting}
It remains to convert this sequence of pairs into the string \lstinline!"abcd"!.
One way of doing this is to project the sequence of pairs onto the
second parts of the pairs,
\begin{lstlisting}
scala> res0.map(_._2).mkString
res1: String = bcd
\end{lstlisting}
We just need to add the first character, \lstinline!'a'!. The resulting
code is
\begin{lstlisting}
def noDups(s: String): String = if (s == "") "" else {
  val pairs = s.zip(s.tail).filter { case (x, y) => x != y }
  pairs.head._1 +: pairs.map(_._2).mkString
}
\end{lstlisting}
The method \lstinline!+:! prepends an element to a sequence, so \lstinline!x +: xs!
is equivalent to \lstinline!Seq(x) ++ xs!.

\subsubsection{Example \label{subsec:ch2Example-seq-10-1}\ref{subsec:ch2Example-seq-10-1}}

For a given sequence of type \lstinline!Seq[A]!, find the longest
subsequence that does not contain any adjacent duplicate values.

\begin{lstlisting}
def longestNoDups[A](xs: Seq[A]): Seq[A] = ???

scala> longestNoDups(Seq(1, 2, 2, 5, 4, 4, 4, 8, 2, 3, 3))
res0: Seq[Int] = List(4, 8, 2, 3)
\end{lstlisting}


\subparagraph{Solution}

This is a \index{dynamic programming}dynamic programming\footnote{\texttt{\href{https://en.wikipedia.org/wiki/Dynamic_programming}{https://en.wikipedia.org/wiki/Dynamic\_programming}}}
problem. Many such problems are solved with a single \lstinline!foldLeft!.
The accumulator represents the current \textsf{``}state\textsf{''} of the dynamic
programming solution, and the \textsf{``}state\textsf{''} is updated with each new
element of the input sequence.

We first need to determine the type of the accumulator value, or the
\textsf{``}state\textsf{''}. The task is to find the longest subsequence without adjacent
duplicates. So the accumulator should represent the longest subsequence
found so far, as well as any required extra information about other
subsequences that might grow as we iterate over the elements of \lstinline!xs!.
What is that extra information in our case? 

Imagine creating the set of \emph{all} subsequences that have no adjacent
duplicates. For the input sequence $\left[1,2,2,5,4,4,4,8,2,3,3\right]$,
this set of all subsequences will be $\{\left[1,2\right],\left[2,5,4\right],\left[4,8,2,3\right]\}$.
We can build this set incrementally in the accumulator value of a
\lstinline!foldLeft!. To visualize how this set would be built, consider
the partial result after seeing the first $8$ elements of the input
sequence, $\left[1,2,2,5,4,4,4,8\right]$. The partial set of non-repeating
subsequences is $\left\{ \left[1,2\right],\left[2,5,4\right],\left[4,8\right]\right\} $.
When we see the next element, $2$, we will update that partial set
to $\left\{ \left[1,2\right],\left[2,5,4\right],\left[4,8,2\right]\right\} $.

It is now clear that the subsequence $\left[1,2\right]$ has no chance
of being the longest subsequence, since $\left[2,5,4\right]$ is already
longer. However, we do not yet know whether $\left[2,5,4\right]$
or $\left[4,8,2\right]$ is the winner, because the subsequence $\left[4,8,2\right]$
could still grow and become the longest one (and it does become $\left[4,8,2,3\right]$
later). At this point, we need to keep both of these two subsequences
in the accumulator, but we may already discard $\left[1,2\right]$.

We have deduced that the accumulator needs to keep only \emph{two}
sequences: the first sequence is already terminated and will not grow,
the second sequence ends with the current element and may yet grow.
The initial value of the accumulator is empty. The first subsequence
is discarded when it becomes shorter than the second. The code can
be written now:
\begin{lstlisting}
def longestNoDups[A](xs: Seq[A]): Seq[A] = {
  val init: (Seq[A], Seq[A]) = (Seq(), Seq())
  val (first, last) = xs.foldLeft(init) { case ((first, current), x) =>
                    // If `current` is empty, `x` is not considered to be repeated.
    val xWasRepeated = current != Seq() && current.last == x
    val firstIsLongerThanCurrent = first.length > current.length
                    // Compute the new pair `(first, current)`.
                    // Keep `first` only if it is longer; otherwise replace it by `current`.
    val newFirst = if (firstIsLongerThanCurrent) first else current
                    // Append `x` to `current` if `x` is not repeated.
    val newCurrent = if (xWasRepeated) Seq(x) else current :+ x
    (newFirst, newCurrent)
  }
                    // Return the longer of the two subsequences; prefer `first`.
  if (first.length >= last.length) first else last
}
\end{lstlisting}


\subsection{Exercises\index{exercises}}

\subsubsection{Exercise \label{subsec:ch2Exercise-seq-1}\ref{subsec:ch2Exercise-seq-1}}

Compute the sum of squared digits of a given integer; e.g., \lstinline!dsq(123) = 14!
(see Example~\ref{subsec:ch2sumdigitsExample-seq-5}). Generalize
the solution to take as an argument an function \lstinline!f: Int => Int!
replacing the squaring operation. The required type signature and
a sample test:
\begin{lstlisting}
def digitsFSum(x: Int)(f: Int => Int): Int = ???

scala> digitsFSum(123){ x => x * x }
res0: Int = 14

scala> digitsFSum(123){ x => x * x * x }
res1: Int = 36
\end{lstlisting}


\subsubsection{Exercise \label{subsec:ch2Exercise-seq-2}\ref{subsec:ch2Exercise-seq-2}}

Compute the \textbf{Collatz sequence\index{Collatz sequence}} $c_{i}$
as a stream defined by
\[
c_{0}=n\quad;\quad\quad c_{k+1}=\begin{cases}
c_{k}/2 & \text{if }c_{k}\text{ is even,}\\
3*c_{k}+1 & \text{if }c_{k}\text{ is odd.}
\end{cases}
\]
Stop the stream when it reaches $1$ (as one would expect\footnote{\texttt{\href{https://en.wikipedia.org/wiki/Collatz_conjecture}{https://en.wikipedia.org/wiki/Collatz\_conjecture}}}
it will).

\subsubsection{Exercise \label{subsec:ch2Exercise-seq-3}\ref{subsec:ch2Exercise-seq-3}}

For a given integer $n$, compute the sum of cubed digits, then the
sum of cubed digits of the result, etc.; stop the resulting sequence
when it repeats itself, and so determine whether it ever reaches $1$.
(Use Exercise~\ref{subsec:ch2Exercise-seq-1}.)
\begin{lstlisting}
def cubes(n: Int): Stream[Int] = ???

scala> cubes(123).take(10).toList
res0: List[Int] = List(123, 36, 243, 99, 1458, 702, 351, 153, 153, 153)

scala> cubes(2).take(10).toList
res1: List[Int] = List(2, 8, 512, 134, 92, 737, 713, 371, 371, 371)

scala> cubes(4).take(10).toList
res2: List[Int] = List(4, 64, 280, 520, 133, 55, 250, 133, 55, 250)

def cubesReach1(n: Int): Boolean = ???

scala> cubesReach1(10)
res3: Boolean = true

scala> cubesReach1(4)
res4: Boolean = false
\end{lstlisting}


\subsubsection{Exercise \label{subsec:ch2Exercise-seq-4}\ref{subsec:ch2Exercise-seq-4}}

For \lstinline!a!, \lstinline!b!, \lstinline!c! of type \lstinline!Set[Int]!,
compute the set of all sets of the form \lstinline!Set(x, y, z)!
where \lstinline!x! is from \lstinline!a!, \lstinline!y! from \lstinline!b!,
and \lstinline!z! from \lstinline!c!. The required type signature
and a sample test:
\begin{lstlisting}
def prod3(a: Set[Int], b: Set[Int], c: Set[Int]): Set[Set[Int]] = ???

scala> prod3(Set(1,2), Set(3), Set(4,5))
res0: Set[Set[Int]] = Set(Set(1,3,4), Set(1,3,5), Set(2,3,4), Set(2,3,5))
\end{lstlisting}

Hint: use \lstinline!flatMap!.

\subsubsection{Exercise \label{subsec:ch2Exercise-seq-5}\ref{subsec:ch2Exercise-seq-5}{*}}

Same task as in Exercise~\ref{subsec:ch2Exercise-seq-4} for a set
of sets: instead of just three sets \lstinline!a!, \lstinline!b!,
\lstinline!c!, a \lstinline!Set[Set[Int]]! is given. The required
type signature and a sample test:
\begin{lstlisting}
def prodSet(si: Set[Set[Int]]): Set[Set[Int]] = ???

scala> prodSet(Set(Set(1,2), Set(3), Set(4,5), Set(6)))
res0: Set[Set[Int]] = Set(Set(1,3,4,6),Set(1,3,5,6),Set(2,3,4,6),Set(2,3,5,6))
\end{lstlisting}

Hint: use \lstinline!foldLeft! and \lstinline!flatMap!.

\subsubsection{Exercise \label{subsec:ch2Exercise-seq-4-1}\ref{subsec:ch2Exercise-seq-4-1}{*}}

In a sorted array \lstinline!xs:Array[Int]! where no values are repeated,
find all pairs of values whose sum equals a given number $n$. Use
tail recursion. A type signature and a sample test:
\begin{lstlisting}
def pairs(goal: Int, xs: Array[Int]): Set[(Int, Int)] = ???

scala> pairs(10, Array(1, 2, 3, 4, 5, 6, 7, 8))()
res0: Set[(Int, Int)] = Set((2,8), (3,7), (4,6), (5,5))
\end{lstlisting}


\subsubsection{Exercise \label{subsec:ch2Exercise-seq-6}\ref{subsec:ch2Exercise-seq-6}}

Reverse a sentence\textsf{'}s word order, but keep the words unchanged:
\begin{lstlisting}
def revSentence(s: String): String = ???

scala> revSentence("A quick brown fox")
res0: String = "fox brown quick A"
\end{lstlisting}


\subsubsection{Exercise \label{subsec:ch2revdigits-Exercise-seq-7}\ref{subsec:ch2revdigits-Exercise-seq-7}}

\textbf{(a)} Reverse an integer\textsf{'}s digits (see Example~\ref{subsec:ch2sumdigitsExample-seq-5})
as shown:
\begin{lstlisting}
def revDigits(n: Int): Int = ???

scala> revDigits(12345)
res0: Int = 54321
\end{lstlisting}
\textbf{(b)} A \textbf{\index{palindrome integer}palindrome integer}
is an integer number \lstinline!n! such that \lstinline!revDigits(n) == n!.
Write a predicate function of type \lstinline!Int => Boolean! that
checks whether a given positive integer is a palindrome.

\subsubsection{Exercise \label{subsec:ch2Exercise-seq-8}\ref{subsec:ch2Exercise-seq-8}}

Define a function \lstinline!findPalindrome: Long => Long! performing
the following computation: First define \lstinline!f(n) = revDigits(n) + n!
for a given integer \lstinline!n!, where the function \lstinline!revDigits!
was defined in Exercise~\ref{subsec:ch2revdigits-Exercise-seq-7}.
If \lstinline!f(n)! is a palindrome integer, \lstinline!findPalindrome!
returns that integer. Otherwise, it keeps applying the same transformation
and computes \lstinline!f(n)!, \lstinline!f(f(n))!, ..., until a
palindrome integer is eventually found (this is mathematically guaranteed).
A sample test:
\begin{lstlisting}
scala> findPalindrome(10101)
res0: Long = 10101

scala> findPalindrome(123)
res0: Long = 444

scala> findPalindrome(83951)
res1: Long = 869363968
\end{lstlisting}


\subsubsection{Exercise \label{subsec:ch2Exercise-seq-8-1-1}\ref{subsec:ch2Exercise-seq-8-1-1}}

Transform a given sequence \lstinline!xs: Seq[Int]! into a sequence
\lstinline!Seq[(Int, Int)]! of pairs that skip one neighbor. Implement
this transformation as a function \lstinline!skip1! with a type parameter
\lstinline!A! instead of the type \lstinline!Int!. The required
type signature and a sample test:
\begin{lstlisting}
def skip1[A](xs: Seq[A]): Seq[(A, A)] = ???

scala> skip1(List(1,2,3,4,5))
res0: List[Int] = List((1,3), (2,4), (3,5))
\end{lstlisting}


\subsubsection{Exercise \label{subsec:ch2Exercise-seq-8-1}\ref{subsec:ch2Exercise-seq-8-1}}

\textbf{(a)} For a given integer interval $\left[n_{1},n_{2}\right]$,
find the largest integer $k\in\left[n_{1},n_{2}\right]$ such that
the decimal representation of $k$ does \emph{not} contain any of
the digits $3$, $5$, or $7$. \textbf{(b)} For a given integer interval
$\left[n_{1},n_{2}\right]$, find the integer $k\in\left[n_{1},n_{2}\right]$
with the largest sum of decimal digits. \textbf{(c)} A positive integer
$n$ is called a \textbf{perfect number\index{perfect number}} if
it is equal to the sum of its divisors (other integers $k$ such that
$k<n$ and $n/k$ is an integer). For example, $6$ is a perfect number
because its divisors are $1$, $2$, and $3$, and $1+2+3=6$, while
$8$ is not a perfect number because its divisors are $1$, $2$,
and $4$, and $1+2+4=7\neq8$. Write a function that determines whether
a given number $n$ is perfect. Determine all perfect numbers up to
one million.

\subsubsection{Exercise \label{subsec:ch2Exercise-seq-9}\ref{subsec:ch2Exercise-seq-9}}

Remove adjacent repeated elements from a sequence of type \lstinline!Seq[A]!
when they are repeated more than $k$ times. Repetitions up to $k$
times should remain unchanged. The required type signature and a sample
test:
\begin{lstlisting}
def removeDups[A](s: Seq[A], k: Int): Seq[A] = ???

scala> removeDups(Seq(1, 1, 1, 1, 5, 2, 2, 5, 5, 5, 5, 5, 1), 3)
res0: Seq[Int] = List(1, 1, 1, 5, 2, 2, 5, 5, 5, 1)
\end{lstlisting}


\subsubsection{Exercise \label{subsec:ch2Exercise-seq-9-1}\ref{subsec:ch2Exercise-seq-9-1}}

Implement a function\index{unfold function@\texttt{unfold} function}
\lstinline!unfold2! with the type signature
\begin{lstlisting}
def unfold2[A,B](init: A)(next: A => Option[(A,B)]): Stream[B]
\end{lstlisting}
The function should create a stream of values of type \lstinline!B!
by repeatedly applying the given function \lstinline!next! until
it returns \lstinline!None!. At each iteration, \lstinline!next!
should be applied to the value of type \lstinline!A! returned by
the previous call to \lstinline!next!. An example test:
\begin{lstlisting}
scala> unfold2(0) { x => if (x > 5) None else Some((x + 2, s"had $x")) }
res0: Stream[String] = Stream(had 0, ?)

scala> res0.toList
res1: List[String] = List(had 0, had 2, had 4) 
\end{lstlisting}


\subsubsection{Exercise \label{subsec:ch2Exercise-seq-11}\ref{subsec:ch2Exercise-seq-11}{*}}

\textbf{(a)} Remove repeated elements (whether adjacent or not) from
a sequence of type \lstinline!Seq[A]!. (This re-implements the standard
library\textsf{'}s method \lstinline!distinct!.)

\textbf{(b)} For a sequence of type \lstinline!Seq[A]!, remove all
elements that are repeated (whether adjacent or not) more than $k$
times:
\begin{lstlisting}
def removeK[A](k: Int, xs: Seq[A]): Seq[A] = ???

scala> removeK(2, Seq("a", "b", "a", "b", "b", "c", "b", "a"))
res0: Seq[String] = List(a, b, a, b, c)
\end{lstlisting}


\subsubsection{Exercise \label{subsec:ch2Exercise-seq-10}\ref{subsec:ch2Exercise-seq-10}{*}}

For a given sequence \lstinline!xs:Seq[Double]!, find a subsequence
that has the largest sum of values. The sequence \lstinline!xs! is
not sorted, and its values may be positive or negative. The required
type signature and a sample test:
\begin{lstlisting}
def maxsub(xs: Seq[Double]): Seq[Double] = ???

scala> maxsub(Seq(1.0, -1.5, 2.0, 3.0, -0.5, 2.0, 1.0, -10.0, 2.0))
res0: Seq[Double] = List(2.0, 3.0, -0.5, 2.0, 1.0)
\end{lstlisting}

Hint: use \index{dynamic programming}dynamic programming and \lstinline!foldLeft!.

\subsubsection{Exercise \label{subsec:ch2Exercise-seq-12}\ref{subsec:ch2Exercise-seq-12}{*}}

Using tail recursion, find all common integers between two \emph{sorted}
sequences:
\begin{lstlisting}
@tailrec def commonInt(xs: Seq[Int], ys: Seq[Int]): Seq[Int] = ???

scala> commonInt(Seq(1, 3, 5, 7), Seq(2, 3, 4, 6, 7, 8))
res0: Seq[Int] = List(3, 7)
\end{lstlisting}


\section{Discussion and further developments}

\subsection{Total and partial functions}

In Scala, functions can be total or partial. A \textbf{\index{total function}total}
function will always compute a result value, while a \textbf{\index{partial function}partial}
function may fail to compute its result for certain values of its
arguments.

A simple example of a partial function in Scala is the \lstinline!max!
method: it only works for non-empty sequences. Trying to evaluate
it on an empty sequence generates an error called an \textsf{``}exception\index{exception}\textsf{''}:
\begin{lstlisting}[mathescape=false]
scala> Seq(1).tail
res0: Seq[Int] = List()
scala> res0.max
java.lang.UnsupportedOperationException: empty.max
  at scala.collection.TraversableOnce$class.max(TraversableOnce.scala:229)
  at scala.collection.AbstractTraversable.max(Traversable.scala:104)
  ... 32 elided 
\end{lstlisting}
This kind of error may crash the entire program at run time. Unlike
the type errors\index{type error} we saw before, which occur at compilation
time (i.e., before the program can start), \textbf{run-time errors}\index{run-time error}
occur while the program is running, and only when some partial function
happens to get an incorrect input. The incorrect input may occur at
any point after the program started running, which may crash the entire
program in the middle of a long computation.

So, it seems clear that we should write code that does not generate
such errors. For instance, it is safe to apply \lstinline!max! to
a sequence if we know that it is non-empty.

Sometimes, a function that uses pattern matching turns out to be a
partial function because its pattern matching code fails on certain
input data. 

If a pattern matching expression fails, the code will throw an exception
and stop running. In functional programming, we usually want to avoid
this situation because it makes it much harder to reason about program
correctness. In most cases, programs can be written to avoid the possibility
of match errors. An example of an unsafe pattern matching expression
is
\begin{lstlisting}[mathescape=false]
def h(p: (Int, Int)): Int = p match { case (x, 0) => x }

scala> h( (1,0) )
res0: Int = 1

scala> h( (1,2) )
 scala.MatchError: (1,2) (of class scala.Tuple2$mcII$sp)
  at .h(<console>:12)
  ... 32 elided 
\end{lstlisting}
Here the pattern contains a pattern variable \lstinline!x! and a
constant \lstinline!0!. This pattern only matches tuples whose second
part is equal to \lstinline!0!. If the second argument is nonzero,
a match error occurs and the program crashes. So, \lstinline!h! is
a partial function.

Pattern matching failures never happen if we match a tuple of correct
size with a pattern such as \lstinline!(x, y, z)!, because a pattern
variable will always match a value. So, pattern matching with a pattern
such as \lstinline!(x, y, z)! is \textbf{infallible}\index{pattern matching!infallible}
(never fails at run time) when applied to a tuple with $3$ elements.

Another way in which pattern matching can be made infallible is by
including a pattern that matches everything:
\begin{lstlisting}
p match {
  case (x, 0)   => ...   // This only matches some tuples.
  case _        => ...   // This matches everything.
}
\end{lstlisting}
If the first pattern \lstinline!(x, 0)! fails to match the value
\lstinline!p!, the second pattern will be tried (and will always
succeed). The \lstinline!case! patterns in a \lstinline!match! expression
are tried in the order they are written. So, a \lstinline!match!
expression may be made infallible by adding a \textsf{``}match-all\textsf{''} underscore
pattern.

\subsection{Scope and shadowing of pattern matching variables\label{subsec:Scope-and-shadowing-variables}}

Pattern matching introduces \textbf{locally scoped\index{local scope}}
variables \textemdash{} that is, variables defined only on the right-hand
side of the pattern match expression. As an example, consider this
code:
\begin{lstlisting}
def f(x: (Int, Int)): Int = x match { case (x, y) => x + y }

scala> f( (2,4) )
res0: Int = 6
\end{lstlisting}
The argument of \lstinline!f! is the variable \lstinline!x! of a
tuple type \lstinline!(Int,Int)!, but there is also a pattern variable
\lstinline!x! in the case expression. The pattern variable \lstinline!x!
matches the first part of the tuple and has type \lstinline!Int!.
Because variables are locally scoped, the pattern variable \lstinline!x!
is only defined within the expression \lstinline!x + y!. The argument
\lstinline!x:(Int,Int)! is a completely different variable whose
value has a different type.

The code works correctly but is confusing to read because of the name
clash between the two quite different variables, both named \lstinline!x!.
Another negative consequence of the name clash is that the argument
\lstinline!x:(Int,Int)! \emph{is invisible} within the case expression:
if we write \textsf{``}\lstinline!x!\textsf{''} in that expression, we will get the
pattern variable \lstinline!x:Int!. One says that the argument \lstinline!x:(Int,Int)!
has been \index{shadowed name}\textbf{shadowed} by the pattern variable
\lstinline!x! (which is a \textsf{``}\index{bound variable}bound variable\textsf{''}
inside the case expression).

The problem is easy to avoid: we can give the pattern variable another
name. Since the pattern variable is locally scoped, it can be renamed
within its scope without affecting any other code:
\begin{lstlisting}
def f(x: (Int, Int)): Int = x match { case (a, b) => a + b }

scala> f( (2,4) )
res0: Int = 6
\end{lstlisting}


\subsection{Lazy values and sequences. Iterators and streams\label{subsec:Lazy-values-iterators-and-streams}}

We have used streams to create sequences whose length is not known
in advance. An example is a stream containing a sequence of increasing
positive integers:
\begin{lstlisting}
scala> val p = Stream.iterate(1)(_ + 1)
p: Stream[Int] = Stream(1, ?)
\end{lstlisting}
At this point, we have not defined a stopping condition for this stream.
In some sense, streams may be seen as \textsf{``}infinite\textsf{''} sequences, although
in practice a stream is always finite because computers cannot run
infinitely long. Also, computers cannot store infinitely many values
in memory. 

More precisely, streams are \textsf{``}partially computed\textsf{''} rather than \textsf{``}infinite\textsf{''}.
The main difference between arrays and streams is that a stream\textsf{'}s
elements are computed on demand and not all initially available, while
an array\textsf{'}s elements are all computed in advance and are immediately
available.

Generally, there are four possible ways a value could be available:
\begin{center}
\begin{tabular}{|c|c|c|}
\hline 
\textbf{\small{}Availability} & \textbf{\small{}Explanation} & \textbf{\small{}Example Scala code}\tabularnewline
\hline 
\hline 
{\small{}\textsf{``}eager\index{eager value}\textsf{''}} & {\small{}computed immediately} & {\small{}}\lstinline!val z = f(123)!\tabularnewline
\hline 
{\small{}\textsf{``}lazy\textsf{''}} & {\small{}computed upon first use} & {\small{}}\lstinline!lazy val z = f(123)!\tabularnewline
\hline 
{\small{}\textsf{``}on-call\textsf{''}} & {\small{}computed each time it is used} & {\small{}}\lstinline!def z = f(123)!\tabularnewline
\hline 
{\small{}\textsf{``}never\textsf{''}} & {\small{}cannot be computed due to errors} & {\small{}}\lstinline!val (x, y) = "abc" !\tabularnewline
\hline 
\end{tabular}
\par\end{center}

A \textbf{lazy value}\index{lazy value} (declared as \lstinline!lazy val!
in Scala) is computed only when it is needed in some other expression.
Once computed, a lazy value stays in memory and will not be re-computed.

An \textsf{``}on-call\textsf{''} value\index{on-call value} is re-computed every
time it is used. In Scala, a \lstinline!def! declaration does that.

Most collection types in Scala (such as \lstinline!List!, \lstinline!Array!,
\lstinline!Set!, and \lstinline!Map!) are \textbf{eager}\index{eager collection}:
all elements of an eager collection are already evaluated.

A stream is a \textbf{lazy\index{lazy collection}} \textbf{collection}.
Elements of a stream are computed when first needed; after that, they
remain in memory and will not be computed again:
\begin{lstlisting}
scala> val str = Stream.iterate(1)(_ + 1)
str: Stream[Int] = Stream(1, ?)

scala> str.take(10).toList
res0: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> str
res1: Stream[Int] = Stream(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ?)
\end{lstlisting}

In many cases, it is not necessary to keep previous values of a sequence
in memory. For example:

\begin{lstlisting}
scala> (1L to 1000000000L).sum        // Compute the sum of integers from 1 to 1 billion.
res0: Long = 500000000500000000
\end{lstlisting}
We do not actually need to put a billion numbers in memory if we only
want to compute their sum. Indeed, the computation just shown does
\emph{not} put all the numbers in memory. The computation will fail
if we use a list or a stream: 
\begin{lstlisting}
scala> (1L to 1000000000L).toStream.sum
java.lang.OutOfMemoryError: GC overhead limit exceeded
\end{lstlisting}

The code \lstinline!(1L to 1000000000L).sum! works because \lstinline!(1 to n)!
produces a sequence whose elements are computed whenever needed but
do not remain in memory. This can be seen as a sequence with the \textsf{``}on-call\textsf{''}
availability of elements. Sequences of this sort are called \textbf{iterators}\index{iterator}:
\begin{lstlisting}
scala> 1 to 5
res0: scala.collection.immutable.Range.Inclusive = Range(1, 2, 3, 4, 5)

scala> 1 until 5
res1: scala.collection.immutable.Range = Range(1, 2, 3, 4)
\end{lstlisting}
The types \lstinline!Range! and \lstinline!Range.Inclusive! are
defined in the Scala standard library and are iterators. They behave
as collections and support the usual methods (\lstinline!map!, \lstinline!filter!,
etc.), but they do not store previously computed values in memory.

\paragraph{The \texttt{view} method}

Eager collections such as \lstinline!List! or \lstinline!Array!
can be converted to iterators by using the \lstinline!view! method.
This is necessary when intermediate collections consume too much memory
when fully evaluated. For example, consider the computation of Example~\ref{subsec:tuples-Example7}
where we used \lstinline!flatMap! to replace each element of an initial
sequence by three new numbers before computing \lstinline!max! of
the resulting collection. If instead of three new numbers we wanted
to compute \emph{three} \emph{million} new numbers each time, the
intermediate collection created by \lstinline!flatMap! would require
too much memory, and the computation would crash:

\begin{wrapfigure}{l}{0.545\columnwidth}%
\vspace{-0.75\baselineskip}
\begin{lstlisting}
scala> (1 to 10).flatMap(x => 1 to 3000000).max
java.lang.OutOfMemoryError: GC overhead limit exceeded
\end{lstlisting}
\vspace{-0.75\baselineskip}
\end{wrapfigure}%

\noindent Even though the range \lstinline!(1 to 10)! is an iterator,
a subsequent \lstinline!flatMap! operation creates an intermediate
collection that is too large for our computer\textsf{'}s memory. We can use
\lstinline!view! to avoid this:

\begin{wrapfigure}{l}{0.545\columnwidth}%
\vspace{-0.75\baselineskip}
\begin{lstlisting}
scala> (1 to 10).view.flatMap(x => 1 to 3000000).max
res0: Int = 3000000
\end{lstlisting}
\vspace{-0.75\baselineskip}
\end{wrapfigure}%

\noindent The choice between using streams and using iterators is
dictated by memory constraints. Except for that, streams and iterators
behave similarly to other sequences. We may write programs in the
map/reduce style, applying standard methods such as \lstinline!map!,
\lstinline!filter!, etc., to streams and iterators. Mathematical
reasoning about transforming a sequence is the same, whether the sequence
is eager, lazy, or on-call.

\paragraph{The \texttt{Iterator} class}

The Scala library class \lstinline!Iterator! has methods such as
\lstinline!Iterator.iterate! and others, similarly to \lstinline!Stream!.
However, \lstinline!Iterator! does not behave as a \emph{value} in
the mathematical sense\index{Scala\textsf{'}s Iterator@Scala\textsf{'}s \texttt{Iterator}}:
\begin{lstlisting}
scala> val iter = (1 until 10).toIterator
iter: Iterator[Int] = non-empty iterator

scala> iter.toList // Look at the elements of `iter`.
res0: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)

scala> iter.toList // Look at those elements again...??
res1: List[Int] = List()

scala> iter
res2: Iterator[Int] = empty iterator
\end{lstlisting}
Evaluating the expression \lstinline!iter.toList! two times produces
a different result the second time. As we see from the Scala output,
the value \lstinline!iter! has become \textsf{``}empty\textsf{''} after the first
use.

This situation is impossible in mathematics: if $x$ is some value,
such as $100$, and $f$ is some function, such as $f(x)=\sqrt{x}$,
then $f(x)$ will be the same, $f(100)=\sqrt{100}=10$, no matter
how many times we compute $f(x)$. For instance, we can compute $f(x)+f(x)=20$
and obtain the correct result. We could also set $y=f(x)$ and compute
$y+y=20$, with the same result. This property is called \index{referential transparency}\textbf{referential
transparency} or \index{pure function}\textbf{functional purity}
of the function $f$. After applying a pure function, we can be sure
that, for instance, no hidden values in memory have been modified.

When we set $x=100$ and compute $f(x)+f(x)$, the number $100$ does
not \textsf{``}become empty\textsf{''} after the first use; its value remains the
same. This behavior is called the \textbf{\index{value semantics}value
semantics} of numbers. One says that integers \textsf{``}are values\textsf{''} in
the mathematical sense. Alternatively, one says that numbers are \textbf{immutable\index{immutable value},}
i.e., cannot be changed. (What would it mean to \textsf{``}modify\textsf{''} the number
$10$?)

In programming, a type has value semantics if a given computation
applied to it always gives the same result. Usually, this means that
the type contains immutable data, and the computation is referentially
transparent. We can see that Scala\textsf{'}s \lstinline!Range! has value
semantics and is immutable:
\begin{lstlisting}
scala> val x = 1 until 10
x: scala.collection.immutable.Range = Range(1, 2, 3, 4, 5, 6, 7, 8, 9)

scala> x.toList
res0: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)

scala> x.toList
res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9) 
\end{lstlisting}
Collections such as \lstinline!List!, \lstinline!Map!, or \lstinline!Stream!
are immutable. Some elements of a \lstinline!Stream! may not be evaluated
yet, but this does not affect its value semantics:
\begin{lstlisting}
scala> val str = (1 until 10).toStream
str: scala.collection.immutable.Stream[Int] = Stream(1, ?)

scala> str.toList
res0: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)

scala> str.toList
res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9) 
\end{lstlisting}
Iterators produced by applying the \lstinline!view! method to collections
will have value semantics:
\begin{lstlisting}
scala> val v = (1 until 10).view
v: scala.collection.SeqView[Int,IndexedSeq[Int]] = SeqView(...)

scala> v.toList
res0: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)

scala> v.toList
res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)
\end{lstlisting}

Due to the lack of value semantics, programs written using \lstinline!Iterator!
may not obey the usual rules of mathematical reasoning. \index{Scala\textsf{'}s Iterator@Scala\textsf{'}s \texttt{Iterator}}This
makes it easy to write wrong code that looks correct.

To illustrate the problem, let us re-implement Example~\ref{subsec:ch2Example-seq-7}
by keeping the same code but using \lstinline!Iterator! instead of
\lstinline!Stream!:
\begin{lstlisting}
def stopRepeatsBad[T](iter: Iterator[T]): Iterator[T] = {
  val halfSpeed = iter.flatMap(x => Seq(x, x))
  halfSpeed.zip(iter) // Do not prepend the first element. It won't help.
  .drop(1).takeWhile { case (h, s) => h != s }
  .map(_._2)
}

scala> stopRepeatsBad(Seq(1, 3, 5, 7, 9, 3, 5, 7, 9).toIterator).toList
res0: List[Int] = List(5, 9, 3, 7, 9)
\end{lstlisting}
The result $\left[5,9,3,7,9\right]$ is incorrect, but not in an obvious
way: the sequence \emph{was} stopped at a repetition, as we wanted,
but some of the elements of the given sequence are missing (while
other elements are present). It is difficult to debug a program that
produces \emph{partially} correct numbers.

The error in this code occurs in the expression \lstinline!halfSpeed.zip(iter)!
due to the fact that \lstinline!halfSpeed! was itself defined via
\lstinline!iter!. The result is that \lstinline!iter! is used twice
in this code, which leads to errors because \lstinline!iter! is mutable
and does not behave as a value. Creating an \lstinline!Iterator!
and using it twice in the same expression can give wrong results or
even fail with an exception:
\begin{lstlisting}
scala> val s = (1 until 10).toIterator
s: Iterator[Int] = non-empty iterator

scala> val t = s.zip(s).toList
java.util.NoSuchElementException: next on empty iterator
\end{lstlisting}
It is surprising and counter-intuitive that a variable cannot be used
twice in some expression. Intuitively, we expect code such as \lstinline!s.zip(s)!
to work correctly even though the variable \lstinline!s! is used
twice. When we read the expression \lstinline!s.zip(s)!, we imagine
a given sequence \lstinline!s! being \textsf{``}zipped\textsf{''} with itself. So
we reason that \lstinline!s.zip(s)! should produce a sequence of
pairs. But Scala\textsf{'}s \lstinline!Iterator! is \textbf{mutable} (can
be modified during use), which breaks the usual ways of mathematical
reasoning about code.\index{Scala\textsf{'}s Iterator@Scala\textsf{'}s \texttt{Iterator}}

The self-modifying behavior of \lstinline!Iterator! is an example
of a side effect. A function has a \index{side effect}\textbf{side
effect} if the function\textsf{'}s code performs some action in addition to
computing the result value. Examples of side effects are: starting
and stopping external processes; modifying values stored in memory;
writing files; printing; sending or receiving data over a network;
and playing sounds. Functions with side effects do not have value
semantics. Calling such a function twice produces the side effect
twice, which is not the same as calling the function once and simply
re-using the result value. On the other hand, \index{pure function}pure
functions have no side effects and have value semantics.

An \lstinline!Iterator! can be converted to a \lstinline!Stream!
using the \lstinline!toStream! method. This restores the value semantics,
since streams are values:
\begin{lstlisting}
scala> val iter = (1 until 10).toIterator
iter: Iterator[Int] = non-empty iterator

scala> val str = iter.toStream
str: Stream[Int] = Stream(1, ?)

scala> str.toList
res0: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)

scala> str.toList
res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)

scala> str.zip(str).toList
res2: List[(Int, Int)] = List((1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (7,7), (8,8), (9,9)) 
\end{lstlisting}
Instead of \lstinline!Iterator!, we can use \lstinline!Stream! and
\lstinline!view! when lazy or on-call collections are required.

Libraries such as \lstinline!scalaz! and \lstinline!fs2! also provide
lazy and on-call streams with correct value semantics.
